某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
A.O(n)
B.
C.O(n2)
D.O(1)
第1题:
设求解某问题的递归算法如下:
F(int n){
if(n=-=1){
Move(1);
}else{
F(n-1);
Move(n);
F(n-1);
}
}
求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(53):设算法Move的计算时间为k,当n=4时,算法F的计算时间为(54)。
A.T(n)=T(n-1)+1
B.T(n)=2T(n-1)
C.T(n)=2T(n-1)+1
D.T(n)=2T(n+1)+1
第2题:
第3题:
设问题规模为n时,某递归算法的时间复杂度记为T(n),已知T(1)=1, T(n)=2T(n/2)+n/2,用O表示的时间复杂度为()
A.O(logn)
B.O(n)
C.O(nlogn)
D.O(n2logn)
第4题:
设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示,则该算法的时间复杂度为(1)。
A.O(lgn)
B.O(nlgn)
C.O(n)
D.O(n2)
第5题:
假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示,则该算法的时间复杂度为()。
A.O(logn)
B.O(n*logn)
C.O(n)
D.O(n^2)