数据结构（三）时间复杂度与大O阶

sdsd

本学习笔记由《大话数据结构》第二章学习整理而来，本学习笔记里涉及的程序是基于C语言的

运行时间是度量时间复杂度的指标，而测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数，运行时间与这个计数成正比。算法时间复杂度的定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况，并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

这样用大写O（）来体现算法时间复杂度的记法，我们称之为大O记法。例如O(n),O(1)。

下面给出分析一个算法时间复杂度大O阶的方法：
推导大O阶：
1.计算出此算法总共的操作执行次数T(n)。
2.用常数1取代运行时间中的所有加法常数。
3.在修改后的运行次数函数中，只保留最高阶项。
4.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
得到的结果就是大O阶。

是不是觉得上面的方法有点抽象呢，下面我们开始举几个例子
一、常数阶O(1)

int sum=0,n=100;   /*执行一次*/
sum=(1+n)*n/2;     /*执行一次*/
printf("%d",sum);   /*执行一次*/

这个算法的操作次数T(n)=3，根据前面的推导大O阶的方法，将3改成1，在保留最高项时，发现其没有最高项。因此这个算法的时间复杂度为O(1)。
对于单纯的分支结构（不含循环结构）而言，执行次数都是恒定的，不随n的变化而变化，其时间复杂度都是O(1)。
二、线性阶O(n)
线性阶的循环结构要复杂一点，要分析算法的复杂度，关键就是要分析循环结构的运行情况。

int i;  /*执行一次*/
for(i=0;i<n;i++) /*执行n+1次*/
{
      sum+=i;  /*执行n次
}

此算法的T(n)=2n+2,根据前面的推导大O阶的方法,可以求出时间复杂度为O(n)
三、对数阶O(logn)
代码如下

int count=1;
while(count<n)
{
     count=count*2;
}

有多少个2相乘后大于n，则会退出循环。由2的x次方为n可以得到x=logn。所以这个循环的时间复杂度为O（logn）
四、平方阶O(logn)

int i,j;  /*执行一次*/
for(i=0;i<n;i++) /*执行n+1次*/
{
     for(j=0;j<n;j++)/*执行n*(n+1)次*/
    {
        sum=sum+i+j;  /*执行n*n次*/
    }      
}

外层循环执行一次，内部循环执行n次，外层需要执行n次，所以内部循环总共执行n*n次。T(n)=1+n+1+n*(n+1)+n*n,,根据前面的推导大O阶的方法,可以求出时间复杂度为O(n^2)

常见的时间复杂度

执行次数函数	阶	非正式术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n^2+2n+1	O(n^2)	平方阶
5logn+20	O(logn)	对数阶
2n+3nlogn+19	O(nlogn)	nlogn阶
6n^3+2n^2+4	O(n^3)	立方阶
2^n	O(2^n)	指数阶

常用的时间复杂度耗费时间从小到大的顺序是：
O(1) <O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3) <O(2^n)<O(n!)<O(n^n)