复杂度分析

文章来源于极客时间前google工程师−王争专栏。

如何分析、统计算法的执行效率和资源消耗？

为什么需要复杂度分析？

测试结果非常依赖测试环境

1. 同样一段代码，用不同的处理器，执行时间不同
2. 不同的代码在不同的机器上运行，执行时间不同

测试结果受数据规模的影响很大

1. 测试数据规模太小，测试结果无法真实的反应算法的性能。
2. 需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率，这就需要复杂度分析。

大O复杂度表示法

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

1
2
3
4
5
6
7
8
9

• 如下代码表示1到n的累加和，估算这段代码的执行时间。
• CPU的角度看，每行代码都执行类似的操作：读数据-运算-写数据。
• 假设每行代码执行的时间相同，都是unit_time，所以这段代码的执行时间就是(2n+2)*unit_time。
• 所有代码的执行时间T(n)与每行代码的执行次数成正比。

所有代码的执行时间T(n)与每行代码的执行次数n成正比

• T(n)代表代码执行的时间
• n表示数据规模的大小
• f(n)代表每行代码执行的次数总和
• 大O时间复杂度实际上并不具体表示代码真正执行的时间
• 表示代码执行时间随数据规模增长的变化趋势，也称渐进时间复杂度，简称时间复杂度
• 当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，都可以忽略

时间复杂度分析

只关注循环次数最多的一段代码

大O这种复杂度只是表示一种变化趋势。所以，我们在分析一个算法，一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

加法法则：总复杂度等于量级最大的那段代码的复杂度

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n){
    int ret = 0;
    int i = 1;
    for(;i<=n;++i){
        ret = ret+f(i);
    }
}
inf f(int n){
    int sum = 0;
    int i=1;
    for(;i<=n;++i){
        sum = sum+1;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们可以把乘法法则看成是嵌套循环。

几种常见的复杂度分析实例

• 多项式量级
  • 常量阶O(1)
  • 对数阶O(logn)
  • 线性阶O(n)
  • 线性对数阶O(nlogn)
  • 平方阶O(n^2) 立方阶O(n^3) k次方阶O(n^k)
• 非多项式量级
  • 指数阶O(2^n)
  • 阶乘阶O(n!)

1.O(1)

O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。如下代码，即便有3行，时间复杂度也是O(1)，而不是O(3)

int i = 8;
int j = 10;
int sum - i+j;
1
2
3

一般情况下，只要算法中不存在循环语句、递归语句，即便有成千上万行的代码，其时间复杂度也为O(1)

2.O(logn) O(nlogn)

对数时间复杂度非常常见，同时也是最难分析的一种时间复杂度。举例如下：

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

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于n时，循环结束。实际上变量i的取值就是一个等比数列

所以这段代码的时间复杂度就是O(log2n)，通过换底公式，我们忽略对数的“底”，统一表示为O(logn)，根据乘法法则，可以很容易理解O(nlogn)，比如归并排序、快速排序的时间复杂度都是O(nlogn)

3.O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定，代码如下：

int cal(int m,int n){
    int sum_1 = 0;
    int i = 1;
    for(;i

void pring(){
    int i = 0;
    int[] a = new int[n];
    for(;i=0;--i){
        print out a[j];
    }
}
1
2
3
4
5
6
7
8
9
10

//n表示array数组的大小
int find(int[] array,int n,int x){
    int i = 0;
    int pos = -1;
    for(int i=0;i