【算法】时间复杂度

一、常用算法复杂度简介

在描述算法复杂度时,经常用到O(1)、O(n)、O(logn)、O(nlogn)来表示对应算法的时间复杂度,

这里进行归纳一下它们代表的含义:

O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

O(n)：

O(n)：时间复杂度为O(n)，代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。

O(n^2)

O(n^2)：就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。
比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。

O(logn)

O(logn)当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍
是比线性还要低的时间复杂度）。
二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

O(nlogn)

O(nlogn)：同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。
归并排序就是O(nlogn)的时间复杂度。

O(1)

O(1)：就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。
哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（哈希冲突不考虑）

二、算法复杂度推导过程

一般用大写O()来表示算法的时间复杂度写法，通常叫做大O记法。

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

O(1)：常数阶

O(n)：线性阶

O(n²)：平方阶

大O推导法：

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

常数阶：

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

View Code

这个算法的运行次数f(n) = 3,根据推导大O阶的方法，第一步是将3改为1，在保留最高阶项是，它没有最高阶项，因此这个算法的时间复杂度为O(1);

另外，

int sum = 0 ; n = 100;        /*执行一次*/
sum = (1+n)*n/2;             /*执行第1次*/
sum = (1+n)*n/2;             /*执行第2次*/
sum = (1+n)*n/2;             /*执行第3次*/
sum = (1+n)*n/2;             /*执行第4次*/
sum = (1+n)*n/2;             /*执行第5次*/
sum = (1+n)*n/2;             /*执行第6次*/
sum = (1+n)*n/2;             /*执行第7次*/
sum = (1+n)*n/2;             /*执行第8次*/
sum = (1+n)*n/2;             /*执行第9次*/
sum = (1+n)*n/2;             /*执行第10次*/
printf("%d",sum);            /*执行一次*/

View Code

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

注意：不管这个常数是多少，3或12，都不能写成O(3)、O(12)，而都要写成O(1)

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

线性阶：

线性阶的循环结构会复杂一些，要确定某个算法的阶次，需要确定特定语句或某个语句集运行的次数。因此要分析算法的复杂度，关键是要分析循环结构的运行情况。

int i;
for(i = 0 ; i < n ; i++){
  /*时间复杂度为O(1)的程序*/      
}

View Code

对数阶：

int count = 1;
while(count < n){
  count = count * 2;
  /*时间复杂度为O(1)的程序*/    
}

View Code

因为每次count*2后，距离结束循环更近了。也就是说有多少个2 相乘后大于n，退出循环。

数学公式：2^x = n --> x = log₂ⁿ

因此这个循环的时间复杂度为O(logn)

平方阶：

int i;
for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < n ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}

View Code

上面的程序中，对于对于内层循环，它的时间复杂度为O(n)，但是它是包含在外层循环中，再循环n次，因此这段代码的时间复杂度为O(n²)。

int i;
for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < m ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}

View Code

但是，如果内层循环改成了m次，时间复杂度就为O(n*m)

再来看一段程序：

int i;
for(i = 0 ; i < n ; i++){
   for(j = i ; j < n ; j++){
    /*时间复杂度为O(1)的程序*/  
    }    
}

View Code

注意：上面的内层循环j = i ;而不是0

因为i = 0时，内层循环执行了n次，当i=1时，执行了n-1次……当i=n-1时，执行了1次，所以总的执行次数为：

n+(n-1)+(n-1)+...+1 =ⁿ⁽ⁿ⁺¹⁾/₂ = n²/₂ + ^_n/₂

根据大O推导方法，保留最高阶项，n²/₂ ，然后去掉这个项相乘的常数，1/2

因此，这段代码的时间复杂度为O(n²)

常见的时间复杂度：

执行次数函数	阶	术语描述
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n²+2n+1	O(n²)	平方阶
5log₂ⁿ+20	O(log₂ⁿ⁾	对数阶
2n+3nlog₂ⁿ+19	O(nlogn)	nlog₂^n阶
6n³+2n²+3n+4	O(n³)	立方阶
2ⁿ	O(2ⁿ)	指数阶

时间复杂度所耗费的时间是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) <O(2ⁿ) < O(n!) <O(nⁿ)