数据结构-算法-时间复杂度

时间复杂度

   顾名思义就是该算法运行的时间，什么样的算法算是高效的算法，无外乎是用最少的内存空间，花最短的时间解决问题的算法就是。所以我们考虑用时间和空间来衡量一个算法的效率，我们来看看定义：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。记做T（n）=O（f（n））

   根据定义，求解算法的时间复杂度的具体步骤是：

   1、找出算法中的基本语句；

      算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体

   2、计算基本语句的执行次数的数量级；

      只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数

   3、用大O记号表示算法的时间性能

   将基本语句执行次数的数量级放到大O记号中

在这里说一下常遇见的几个时间复杂度：

O（1）：常数阶      O（n）：线性阶    O（n^2）:平方阶

推导大O阶的方法

   推导规则：

   1、用常数1取代运行时间中所有加法常数。

   2、其次，只保留最高阶项。

   3、如果阶项系数存在且不为1，则去掉这个系数。

   最终得到的就是大O阶，简单说就是保留求出数的最高次幂，并且把系数去掉，如：(T)=2n^2+n+1=O(n^2)

常数阶

<span style="font-family:KaiTi_GB2312;font-size:24px;">int main()  
{  
    int sum = 0, n = 100;   /* 执行1次 */  
    sum = (1 + n) * n/2;    /* 执行1次 */  
  
    printf("%d", sum);      /* 执行1次 */  
} </span>           

   分析：算法运行次数的函数f(n)=3,根据上面的推导规则，第一步将3改为1，再保留最高阶项，它没有最高阶项，所以算法时间复杂度应该是O（1），注意：只是用执行次数来衡量时间复杂度，但执行次数并不等于时间复杂度，无论输入规模n为多少，执行时间总是恒定的，时间复杂度总是O（1）

再来看一段代码：

<span style="font-family:KaiTi_GB2312;font-size:24px;">int sum = 0 ; n = 100;        /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
sum = (1+n)*n/2;             /*执行1次*/
printf("%d",sum);            /*执行1次*/</span>           

   分析：上面的两端代码中，无论n有多少个，本质只是3和12次的执行差异，这种与问题的大小无关，执行时间恒定的算法，成为具有O(1)的时间复杂度，又叫做常数阶。

   此外，对于分支结构而言，无论真假执行的次数都是恒定不变的，不会随着n的变大而发生变化，所以单纯的分支结构（不在循环结构中），其时间复杂度也是O(1)。

线性阶

<span style="font-family:KaiTi_GB2312;font-size:24px;">int main()  
{  
    int i, sum = 0, n = 100;    /* 执行1次 */  
    for( i = 1; i <= n; i++) /* 执行 n+1 次 */  
    {  
        sum = sum + i;          /* 执行n次 */  
        //printf("%d \n", sum);  
    }  
    printf("%d", sum);          /* 执行1次 */  
}  
</span>           

   分析：该算法所用的时间为：1+（n+1）+n=2n+3，但是虽然n不断增大，n是一个特别特别大的数，那么上述算法的执行时间会随着n的增大而增加，但是第一行和最后一行，也就是for循环以外的语句并不受n的规模影响，永远就执行一次，那么我们可以将上述算法的执行执行总数简单记做：2n或者n，这样我们就得到了这个算法的时间复杂度：O（n）

平方阶

<span style="font-family:KaiTi_GB2312;font-size:24px;">int i;                  /* 执行1次 */ 
for(i = 0 ; i < n ; i++){            /* 执行n+1次 */  
   for(j = 0 ; j < n ; j++){         /* 执行n*（n+1）次 */ 
    /*时间复杂度为O(1)的程序*/       /* 执行1次 */ 
    }    
}</span>           

   分析：该算法的所有语句的频度之和为：T（n）=n^2+2n+3.利用推导规则该算法的时间复杂度应该为O（n^2）；或者可以这么理解：对于内层，时间复杂度为O（n），但是它是包含在外层循环中，再循环n次，因此这段代码的时间复杂度为O(n^2)

常见的时间复杂度

时间复杂度所耗费的时间

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2n) < O(n!) <O(n^n)