算法复杂度习题

一、选择题

1.个算法应该是（ ）。

A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D. A和C 2.某算法的时间复杂度为O(n2)，表明该算法的（ ）。 A.问题规模是n2 B.执行时间等于n2

C.执行时间与n2成正比 D.问题规模与n2成正比

3.以下算法的时间复杂度为（ ）。 void fun(int n) { int i=l;

while(i<=n) i=i*2; }

A. O(n) B. O(n2) C. O(nlog2n) D. O(log2n)

4.【2011年计算机联考真题】

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 x=2;

while(x

A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)

5.【2012年计算机联考真题】

求整数n (n>=0)阶乘的算法如下，其时间复杂度是（ ）。 int fact(int n){

if (n<=l) return 1; return n*fact(n-1); }

A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)

6.有以下算法，其时间复杂度为（ ）。 void fun (int n){ int i=0;

while(i*i*i<=n) i++; }

A. O(n) B. O(nlogn) C. D.

7.程序段

for(i=n-l;i>l;i--) for(j=1;jA[j+l])

A[j]与 A[j+1]对换;

其中n为正整数，则最后一行的语句频度在最坏情况下是（ ）。

A. O(n) B. O(nlogn) C. O(n3) D. O(n2)

8.以下算法中加下划线语句的执行次数为（）。 int m=0, i, j; for(i=l;i<=n;i++)

for(j=1;j<=2*i;j++) m++;

A. n(n+1) B. n C. n+1 D. n2

9.下面说法错误的是（ ）。

Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间

Ⅱ.在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 Ⅲ.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 Ⅳ.同一个算法，实现语言的级别越高，执行效率就越低. A. Ⅰ B. Ⅰ、Ⅱ C. Ⅰ、Ⅳ D. Ⅲ

二、综合应用题

1.一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶)。

式中，n是问题的规模，为简单起见，设n是2的整数幂。

2.分析以下各程序段，求出算法的时间复杂度。

01.// 程序段① 02.i=l;k=0; 03.while(i

08.// 程序段② 09.y=0;

10.while((y+1)*(y+1)<=n) 11. y=y+1; 12.

13.// 程序段③ 14.for(i=l;i<=n;i++)

15. for(j =1;j <=i;j ++) 16. for(k=l;k<=j;k++) 17. x++;

18.

19.// 程序段④ 20.for(i=0;i

21. for(j=0;j