01、数据结构与算法C++：算法时间复杂度-程序员快看-教程，程序员编程资料站

算法时间复杂度

要判断算法的好坏，可以从时间方面进行分析。算法运行的越快，所用的时间越短则算法越好。但是同一个算法在不同的平台上的运行时间不同。那么又该如何进行评判呢？我们采用时间复杂度进行衡量。

算法时间复杂度定义
在进行算法分析时，语句总的执行次数$ T ( n ) 是关于问题规模是关于问题规模是关于问题规模 n 的函数，进而分析的函数，进而分析的函数，进而分析 T ( n ) 随随随 n 的变化情况并确定的变化情况并确定的变化情况并确定 T ( n ) 的数量。算法的时间复杂度。也就是算法的时间量度，记做：的数量。算法的时间复杂度。也就是算法的时间量度，记做：的数量。算法的时间复杂度。也就是算法的时间量度，记做： T ( n )=O(f(n)) 。它表示随问题规模。它表示随问题规模。它表示随问题规模 n 的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和 f ( n ) 的增长率相同，称作算法的 ∗ ∗ 渐近时间复杂度 ∗ ∗ ，简称为 ∗ ∗ 时间复杂度 ∗ ∗ 。其中的增长率相同，称作算法的**渐近时间复杂度**，简称为**时间复杂度**。其中的增长率相同，称作算法的∗∗渐近时间复杂度∗∗，简称为∗∗时间复杂度∗∗。其中 f ( n ) 是问题规模是问题规模是问题规模 n$的某个函数。

简单的理解时间复杂度就是用来表示执行次数$ T ( n ) 随问题规模随问题规模随问题规模 n 增加的变化趋势。 ∗ ∗ 一般情况下，随着增加的变化趋势。**一般情况下，随着增加的变化趋势。∗∗一般情况下，随着 n 的增大，的增大，的增大， T ( n )$增长最慢的算法为最优算法。**

那么如何分析一个算法的时间复杂度呢?步骤如下：

1、用常数1取代运行时间中的所有加法常数；
2、再修改后的运行次数函数中，只保留最高阶项；
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数；

时间复杂度 O ( 1 ) O(1) O(1)

int a=1,b=3,sum=0;//执行1次
sum=a+b;//执行1次
cout<<"sum="<<sum<<endl;//执行1次

时间复杂度 O ( n ) O(n) O(n)

for(int i = 0; i < n; i++)//执行n次
{
    cout<<i<<endl;
}

时间复杂度 O ( n 2 ) O(n^2) O(n2)

for(int i = 0; i < n; i++)//执行n^2次
{
    for(int j = 0; j < n; j++)
    {
        cout<<i<<endl;
    }
}

综上，我们可以看出，若每层嵌套的时间复杂度为 O ( n ) O(n) O(n)，则 n n n层嵌套的时间复杂度为 O ( n n ) O(n^n) O(nn)。

时间复杂度 O ( l o g n ) O(logn) O(logn)

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

由于每次执行i乘以2，当 2 x < n 2^x<n 2x<n时结束循环。所以总共执行了 x = l o g 2 n x=log_2n x=log2n次，所以其时间复杂度为 O ( l o g n ) O(logn) O(logn)。

常用的时间复杂度所耗费的时间从小到大依次是：
O( 1 ) < O ( l o g n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

最坏情况

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

平均情况

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。

递归算法的时间复杂度求解

递归算法的时间复杂度的求解方法有很多，我们这里介绍一个比较常用的求解方法——主方法。
对于递归式：
T( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n)

其中 a ≥ 1 a≥1 a≥1和 b > 1 b>1 b>1是常数， f ( n ) f(n) f(n)是渐近正函数。

1、若对某个常数*>0*>0*>0,有f(n)=O(n(logba)−*)f(n)=O(n^{(log_ba)-*})f(n)=O(n(logba)−*),则T(n)=*(nlogba)T(n)=\Theta(n^{log_ba})T(n)=*(nlogba)；
2、若f(n)=*(nlogba)f(n)=\Theta(n^{log_ba})f(n)=*(nlogba),则T(n)=*(nlogbalgn)T(n)=\Theta(n^{log_ba}lgn)T(n)=*(nlogbalgn)；
3、若对某个常数*>0*>0*>0,有f(n)=*(n(logba)+*)f(n)=\Omega(n^{(log_ba)+*})f(n)=*(n(logba)+*)，且对于某个常数c<1c<1c<1和所有足够大的nnn有$af(n/b)≤cf(n)，则，则，则T(n)=\Theta(f(n))$；

举个栗子： T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T(n)=4T(n/2)+n，其中 a = 4 , b = 2 a=4,b=2 a=4,b=2, l o g b a = 2 log_ba=2 logba=2。当 * = 1 *=1 *=1，有 O ( n ( l o g b a ) − * ) = O ( n ( l o g 2 4 ) − 1 ) = O ( n ) O(n^{(log_ba)-*})=O(n^{(log_24)-1})=O(n) O(n(logba)−*)=O(n(log24)−1)=O(n)。符合第一种情况所以 T ( n ) = * ( n 2 ) T(n)=\Theta (n^{2}) T(n)=*(n2)。