用主定理求解递推方程T(n)=T(2n/3)+1=O(______ )
logn
举一反三
- T(n)=2*T(n/2)+ O(n),该递归方程描述的算法时间复杂度是 A: O(n2) B: O(nlog2n) C: O(2n) D: O(n)
- 给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
- 二分搜索算法的时间复杂度函数,下述那个正确? A: T(n)=O(1),当n=0<br> T(n)=2T(n/2)+O(1),当n>1 B: T(n)=O(1),当n=0<br> T(n)=2T(n/2)+O(n),当n>1 C: T(n)=O(1),当n=0<br> T(n)=T(n/2)+O(1),当n>1 D: T(n)=O(1),当n=0<br> T(n)=T(n/2)+O(n),当n>1
- 求n!问题,表示算法的复杂性的递归函数下述正确的是? A: T(n)=O(1),当n=1 T(n)=T(n-1)+O(1),当n>1 B: T(n)=O(1),当n=1 T(n)=nT(n-1)+O(1),当n>1 C: T(n)=O(1),当n=1 T(n)=2T(n/2)+O(1),当n>1 D: T(n)=O(1),当n=1 T(n)=T(n/2)+O(n),当n>1
- 某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为(53)。 A: O(n) B: O(nlog2n) C: O(n2) D: O(1)
内容
- 0
分治法求棋盘覆盖问题的递推式 A: T(n)=1,n=0T(n)=2T(n/2)+1,n>0 B: T(n)=1,n=0T(n)=T(n/2)+O(n),n>0 C: T(n)=1,n=0T(n)=4T(n-1),n>0 D: T(n)=1,n=0T(n)=2T(n-1),n>0
- 1
某算法的执行时间的递推关系如下:T(n)=1 当n=1时T(n)=2T(n/2)+1 当n>;1时则该算法的时间复杂度为( )。 A: O(1) B: O(log�) C: O(n) D: O(nlog�)
- 2
主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程, 则下列关于方程中的约束中不准确的是?
- 3
主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程, 则下列关于方程中的约束中不准确的是?设6c393a2a3f08bbff105edc32710e2e7f
- 4
设问题规模为N时,某递归算法的时间复杂度记为T(),已知T(1)=1,T()=2T(N/2)+N/2,用O表示的时间复杂度为()。 A: O(logN) B: O(N) C: O(NlogN) D: O(N²logN)