计算算法时间复杂度

1、常见的算法的时间复杂度比较：

常见的算法时间复杂度由小到大依次为：

　　Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n2)＜Ο(n3)＜…＜Ο(2)＜Ο(n!)

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(logn)、Ο(n)、Ο(nlogn)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。

这只能基本的计算时间复杂度，具体的运行还会与硬件有关。

2、计算时间复杂度的相关题目;

一、单项选择题

1.一个算法应该是（ ）。

A.程序    B.问题求解步骤的描述    C.要满足五个基本特性    D. A和C

1.    B

程序不一定满足有穷性，如死循环、操作系统等，而算法必须有穷。算法代表了对问题求解步骤的描述，而程序则是算法在计算机上的特定的实现。

2.某算法的时间复杂度为O(n2)，表明该算法的（ ）。

A.问题规模是n2    B.执行时间等于n2

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

2.    C

时间复杂度为O(n2)，说明算法的执行时间T(n)<=c * n2(c为比例常数)，即T(n)=O(n2)，时间复杂度T(n)是问题规模n的函数，其问题规模仍然是n而不是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)

3.    D

基本运算是i=i*2，设其执行时间为T(n)，则2T(n)<=n，即T(n)<=log2n=O(log2n)。

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

x=2;

while(x<n/2)

    x=2*x;

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

4.    A

在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了 t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2，得 T(n)=O(log2n)。

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)

5.    B

本题是求阶乘n!的递归代码，即n*(n-1)*...*1共执行n次乘法操作，故T(n)=O(n)。

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;j<i;j++)

       if (A[j]>A[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