软考中级
设某算法的计算时间表示为递推关系式T(n)＝T(n-1)+n(n＞O)及T(0)＝1，则该算法的时间复杂度为(65)。A．O(lgn)B．O (nlgn)C．O(n)D．O(n2)
题目
设某算法的计算时间表示为递推关系式T(n)＝T(n-1)+n(n＞O)及T(0)＝1，则该算法的时间复杂度为(65)。
A．O(lgn)
B．O (nlgn)
C．O(n)
D．O(n2)
参考答案和解析
解析：本题考查算法设计基础知识。根据题目中给出的递推关系：T(n)＝T(n-1)+n＝T(n-2)+n-1+n＝…＝T(0)+1+2+…+n-1+n＝1+n(n+1)/2
相似问题和答案
第1题：
假设某算法的计算时间可用递推关系式T（n)=2T（n/2)+n表示，则该算法的时间复杂度为（）。
A．O(logn)
B．O(n*logn)
C．O(n)
D．O(n^2)
第2题：
B.O（nlgn）
C.O（n）
D.O（n^2）
第3题：
设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(1)。
A．O(lgn)
B．O(nlgn)
C．O(n)
D．O(n2)
解析：运用数学递推公式，可以推算出数量级O(nlgn)。
第4题：
设求解某问题的递归算法如下：
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
解析：本题考查对计算杉1算法进行时间复杂度分析的基本方法。直接递归算法的计算时间可以根据递归调用形式对应写出其递推关系式。按照题目中描述的算法形式，可知算法F的计算时间T(n)的递推关系式为T(n)=2T(n-1)+1，其中两次递归调用F(n-1)用时2T(n-1)，算法Move的计算时间为常数，计为1。将上述递推关系式中常数1用k替换，求解可得T(n)=2n-1T(1)+
，易知 T(1)=k，将n=4代入可得计算时间为15k。
第5题：
设求解某问题的递归算法如下：
F(int n){
if n=1 {
Move(1)
}else{
F(n-1)；
Move(n)；
F(n-1)；
}
}
求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(9)；设算法Move的计算时间为k，当 n=4时，算法F的计算时间为(10)。
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
第6题：
计算N!的递归算法如下，求解该算法的时间复杂度时，只考虑相乘操作，则算法的计算时间T(n)的递推关系式为(55)；对应时间复杂度为(56)。
int Factorial (int n)
{//计算n!
if(n＜=1)return 1;
else return n * Factorial(n-1);
}
(62)
A．T(n)=T(n-1)+1
B．T(n)=T(n-1)
C．T(n)=2T(n-1)+1
D．T(n)=2T(n-1)-1
第7题：
● 设某算法的计算时间表示为递推关系式T(n)= T(n-1) + n (n>0) 及T(0)=1，则该算法的时间复杂度为 （65） 。
第8题：
假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n，T(1)=1表示，则该算法的时间复杂度为()
A.O(logn)
B.O(n*logn)
C.O(n)
D.O(n^2)
第9题：
设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(59)。
A．O(1gn)
B．O(nlgn)
C．O(n)
D．O(n2)
解析：本题考查的是算法的时间复杂度概念。