● 某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为（63）。（63）A. O(n2) B. O (n) C. O (n1gn) D. O (1)

● 某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为（63）。

（63）A. O(n2) B. O (n) C. O (n1gn) D. O (1)

第1题：

设某算法的计算时间表示为递推关系式T（n）＝T（n-1）+n（n＞O）及T（0）＝1，则该算法的时间复杂度为（）。

A.O（lgn）
B.O（nlgn）
C.O（n）
D.O（n^2）

答案：D
解析：
本题考查算法设计基础知识。根据题目中给出的递推关系：T（n）＝T（n-1）+n＝T（n-2）+n-1+n＝…＝T（0）+1+2+…+n-1+n＝1+n（n+1）/2
第2题：

设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为O（n）

错误
第3题：

7、设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为O（n）

Ο(1);Ο（1）;Ο(1)Ο(n*logn);Ο(nlogn)
第4题：

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍。

A.O(n)
B.O(nlgn)
C.O(n2)
D.O(n2lgn)

答案：C
解析：
对于递归式，假设T(1)=1，则：
T(n)=T(n-1)+n
=T(n-2)+n-1+n
=T(n-3)+n-2+n-1+n
=1+2+…+n-1+n
=n(n+1)/2
可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。
第5题：

设问题规模为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)

0(N1ogN)

● 某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为 （63）。（63）A. O(n2) B. O (n) C. O (n1gn) D. O (1)