1.2.2 算法的时间复杂度分析

接下来运用上述推导大O阶的方法进行常见算法的时间复杂度分析。

1.O(1)

void pt(int n)
{ 
     int m=0;              /*执行1次*/   
     m=2*n+n/5+6;            /*执行1次*/   
     printf("%d",m);         /*执行1次*/ 
 }

这个算法是由使用顺序结构的语句构成的，算法的运行次数函数T(n)=3。根据大O阶的推导步骤，把常数项3改为1，因此求出该算法的时间复杂度为O(1)。

假设现在修改该算法，执行语句m=2*n+n/5+6五遍，算法如下：

void pt(int n)
 { 
     int m=0;              /*执行1次*/   
     m=2*n+n/5+6;            /*执行1次*/  
     m=2*n+n/5+6;            /*执行1次*/   
     m=2*n+n/5+6;            /*执行1次*/   
     m=2*n+n/5+6;            /*执行1次*/   
     m=2*n+n/5+6;            /*执行1次*/   
     printf("%d",m);         /*执行1次*/ 
  }

这个算法的运行次数函数T(n)=7。根据大O阶的推导步骤，把常数项7改为1，因此求出该算法的时间复杂度也是O(1)。

由上面两个例子可以看出，不管n的值是多少，第一个算法和第二个算法的执行次数始终都是3次和7次，这类算法的执行次数与问题规模n没有关系，算法的时间复杂度始终为O(1)。

2.O(n)

在算法的基本结构中，主要有三种：顺序结构、选择结构和循环结构。顺序结构的语句一般都是O(1)（循环体内的除外）。选择结构中，无论选择哪个分支运行，执行次数都是不变的，不会随着n的变大而增加，因此选择结构一般也是O(1)（循环体内的除外）。循环结构相对于前两者来说就会复杂一些，我们需要计算出基本语句的运行次数，以此确定算法的阶次，此时需要分析循环结构内基本语句的执行情况。

void sum(int n)
 { 
     int i;                    /*执行1次*/ 
     int sum=0;              /*执行1次*/ 
     for(i=0; i<n; i++) 
     {                 
          sum=sum+i;         /*执行n次*/   
     }                   
     printf("%d", sum);        /*执行1次*/ 
  }

这个算法的运行次数函数T(n)=n+3。根据大O阶的推导步骤，求出该算法的时间复杂度是O(n)。此时算法的执行次数随问题规模n的增加而增加，两者是线性关系，因此称这类算法的时间复杂度为线性阶。

3.O(log2n)

void power sum(int n)
 { 
     int i=0;                  /*执行1次*/ 
     int sum=0;              /*执行1次*/ 
     while（i<n） 
     {                 
         sum=sum+i;          /*执行log2n次*/ 
         i=i*2;                /*执行log2n次*/ 
     }                   
     printf("%d", sum);        /*执行1次*/ 
  }

这个算法的关键在于分析循环体内基本语句的执行次数，即计算循环的执行次数。循环变量i的初始值为1，每次循环让i=i×2，循环条件也就转换为判断多少个2相乘后大于n，如果满足条件，就结束循环。假设循环次数为c，由于2×c=n，算出c=log2n。由此算出该算法的运行次数函数T(n)=2×log2n+3。根据大O阶的推导步骤，求出该算法的时间复杂度是O(log2n)。

4.O(n2)

void sum1(int n)
 {   
     int i,j;                         /*执行1次*/ 
     int sum=0;                     /*执行1次*/ 
     for(i=0; i<n; i++) 
        for(j=0; i<n; j++)
           {                 
               sum=sum+i*j;         /*执行n2次*/   
           }                   
     printf("%d", sum);               /*执行1次*/ 
  }

这个算法使用了双重循环，内层循环在前面已经分析过，时间复杂度是O(n)。在内层循环的外面再加上一层循环，其实也就是把循环体内时间复杂度为O(n)的语句，再执行n次，因此得出该算法的时间复杂度为O(n2)。

下面对这个算法进行修改：

void sum2(int m, int n)
{ 
     int i,j;                         /*执行1次*/ 
     int sum=0;                     /*执行1次*/ 
     for(i=0; i<m; i++) 
        for(j=0; j<n; j++)
           {                 
                sum=sum+i*j;        /*执行m*n次*/   
           }                   
     printf("%d", sum);               /*执行1次*/ 
 }

此时这个算法仍采用双重循环，内层循环的时间复杂度还是O(n)，只不过外层循环的执行次数变成了m次，也就是把循环体内时间复杂度为O(n)的语句再执行m次，因此得出该算法的时间复杂度为O(m×n)。

再来看看下面这个算法，它的时间复杂度是多少呢？

void sum3(int n)
{ 
     int i,j;                         /*执行1次*/ 
     int sum=0;                     /*执行1次*/ 
     for(i=0; i<n; i++) 
        for(j=i; j<n; j++)
           {                 
                sum=sum+i*j;        /*执行(n2+n)/2次*/   
           }                   
     printf("%d", sum);               /*执行1次*/ 
 }

这个算法同样采用了双重循环，但是内层循环的执行次数不再是n了，需要重新计算，此时内层循环的执行次数与i的值有关。当i=0时，内层循环的执行次数是n；当i=1时，内循环的执行次数是n-1；当i=2时，内循环的执行次数是n-2；以此类推，当i=n-1时，内循环的执行次数是1次，总的执行次数为：

T(n)=n+(n-1)+(n-2)+…+1+3=(n2+n)/2+3

根据大O阶的推导步骤，得出该算法的时间复杂度是O(n2)。

刚才介绍了O(1)、O(n)、O(log2n)和O(n2)，除了上述四种以外，还有O(n log2n)、O(n3)等时间复杂度。下面按由快到慢的顺序列出当n足够大时，常见的几种大O阶运行时间并进行对比，详见图1.5和表1.7：

O(log2n)<O(n)<O(n log2n)<O(n2)<…<O(2n)<O(n!)

图1.5 常见的大O函数图

表1.7 常见的大O运行时间

一个问题的解可能有多个，这时候在选择和设计算法的时候就要尽量选择时间复杂度低的算法。上述算法中，O(2n)和O(n !)是不切实际的时间复杂度，理论上可行，但实际上不可行，在解决问题时应当尽量避免使用此类算法。

上一章目录下一章