数据结构与算法：复杂度分析

数据结构与算法本身是为了让代码运行得更快，更省存储空间；那么如何考量一个算法的执行效率？这里就要用到时间、空间复杂度分析。

一、为什么需要复杂度分析

有人会觉得把代码放在实际环境中测试一遍，对结果进行统计和监控就能得到算法准确的执行效率，因此不需要对代码做时间和空间复杂度分析，但其实这种分析方法带有一定的局限性。

首先，测试结果非常依赖测试环境，用同一段代码在不同性能的处理器上运行，性能高的处理器的执行速度肯定要比性能低的速度快；在不同的机器上，两段不同的代码执行速度的比较也会有所差别。因此测试环境中硬件的不同会对测试结果有很多的影响。

其次，测试结果受数据规模的影响很大，拿排序算法举例，假如输入进一个排序算法的数据是有序的，那么排序算法便不需要做任何操作，执行时间便会非常短；除此之外，对于同一个算法，算法的数据规模不一样，执行时间会有很大的差别，数据规模太小可能无法反应算法的真实性能，比如对于小规模的数据排序，插入排序可能会比快速排序要快得多。

因此我们需要一种不用具体数据来测试，就能粗略估计算法执行效率的方法，所以我们才要对算法进行时间和空间复杂度分析。

二、大O复杂度表示法

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

上面这段代码是求 1 到 n 累加的和，我们假设每一行代码的执行时间都一样，为 time ，那么第 2、3 行代码分别需要 1 个 time 的执行时间，而第 4、5 行都运行了 n 遍 ，需要 2n*time ，假设这段代码的执行时间为 T(n) ，我们可以粗略估计这段代码运行需要 T(n)=(2n+2)*time 的执行时间。

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

按照刚才的假设，这段代码中第 7、8 行代码循环了 n² 遍，因此代码的总执行时间为 T(n)=(2n²+2n+3)*time，尽管不知道 time 的具体值，我们也能得出，代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

用大O复杂度表示如下:

其中 T(n) 表示代码执行时间，n 表示数据的规模，f(n) 表示每行代码的执行次数总和（如上述的 2n+3 ），O 表示代码执行时间 T(n) 与 f(n) 表达式成正比。

由于是粗略估计，当公式中的 n 很大时，公式中的 低阶、常量、系数都不会左右它的增长趋势，因此我们可以把它们忽略，只需记录一个最大的量级，如上面两端代码的时间复杂度就可以记为 T(n)=O(n)；T(n)=O(n²) 。

三、时间复杂度分析

对代码进行时间复杂度分析有三种方法：

1. 关注执行次数最多的那一行代码

由于公式中的 低阶、常量、系数 对大 O 的影响不大，因此在分析代码的时间复杂度的时候我们只需记录最大阶的量级就可以了，即执行次数最多的代码段。

像上面第一段代码中，执行次数最多的是第 4、5 行代码，这两段代码都被执行了 n 次，因此时间复杂度为 O(n)；第二段代码的 O(n²) 也是一个道理。

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

int cal(int n) { 
    int sum1 = 0,p = 1;
    for(; p < 100; ++p) {
        sum1 = sum1 + p;
    }

    int sum2 = 0,q = 1;
    for(; q < n; ++q) {
        sum2 = sum2 + q;
    }

    int sum3 = 0,i = 1,j = 1;
    for(; i <= n; ++i) {
        for(; j <=n; ++j) {
            sum3 = sum3 + i*j;
        }
    }

    return sum1 + sum2 + sum3;
}

这段代码分为三个部分，sum1 ，sum2 ，和 sum3 ，从之前的结论可以得出这三段代码的复杂度分别为 O(1) ；O(n) ；O(n²)。我们取其中最大的量级，整段代码的时间复杂度便为 O(n²) 。因此说 总的时间复杂度等于量级最大的那段代码的复杂度 。用公式表示为：

T1(n) = O(f(n)) ，T2(n) = O(g(n))
T(n) = T1(n) + T2(n) = Max ( O(f(n)) , O(g(n)) ) = O( Max( f(n) , g(n) ) )

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

int cal(int n) {
    int ret = 0;
    int i = 1;
    for (; i <= n; ++i) {
        ret = ret + f(i);
    }
}

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

类比加法法则，乘法法则的公式是这样的:

T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( ( f(n) * g(n) )

上面代码中，由于 f() 被嵌套在了 cal() ，而 f(n) 的时间复杂度为 O(n) ，因此套用刚才的结论和公式可以得到整个 cal() 的时间复杂度为 O(n²)。

四、几种常见时间复杂度分析

常用的复杂度量级有以上几个，他们可以粗略地分为 多项式量级 和 非多项式量级

非多项式量级

非多项式量级只有两个 O(2ⁿ) 和 O(n!)。
非多项式量级的算法有一个特点，当 n 的规模越来越大时，非多项式量级的算法的执行时间会急剧增加，求解问题的执行时间也会无限增长，因此非多项式量级的算法是非常低效的算法。一般把非多项式量级的算法问题叫做非确定多项式问题。

多项式量级

1. O(1)

int i = 1;
int j = 1;
int sum = i + j;

O(1) 是常量级时间复杂度的一种表示方法；只要代码的执行时间不随着 n 规模的增大而增长，或者说代码中没有循环或递归语句，那么其时间复杂度都是 O(1) 。

2. O(logn) 、 O(nlogn)

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

上面代码中第 3 行执行的次数最多，且每循环一次就乘以 2 ，实际上这就是一个等比数列
我们如果求出 x 的值就能知道代码的执行次数，2^x = n ，所以 x = log₂n ，所以这段代码的时间复杂度就是 O(log₂n)。实际上不论以 2 为底还是其他数字，我们都把所有对数阶的时间复杂度写成 O(logn)；因为对数之间是可以互相转换的。

将上述时间复杂度为 O(logn) 的代码循环执行 n 遍，它的时间复杂度便为 O(nlogn)；这两种都是很常见的算法的时间复杂度，如归并排序和快速排序。

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

int cal(int m,int n) {
    int sum1 = 1;
    int i = 1;
    for (; i < m; ++i) {
        sum1 = sum1 + i;
    }

    int sum2 = 1;
    int j = 1;
    for (; j < n; ++j) {
        sum2 = sum2 + j
    }

    return sum1 + sum2;
}

上面代码中，m 和 n 是表示两个数据规模，不能用简单的加法规则省略掉其中一个，因此上面代码的时间复杂度为 O(m+n)；但有不同数据规模时乘法法则依然有效。

五、空间复杂度分析

时间复杂度全称是 渐进时间复杂度，表示 算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度的全程就是 渐进空间复杂度，它表示 算法的存储空间与数据规模之间的增长关系。

void print(int n) {
    int i = 0;
    int[] a = new int[n];
    for (i; i < n; ++i) {
        a[i] = i * i;
    }
    for (i = n-1; i >=0; --i) {
        print out a[i];
    }
}

跟时间复杂度一样，上面代码中第 2 行申请了一个空间存储变量 i ，但是是常量阶的，可以忽略，第 3 行申请了一个大小为 n 的数组，除此之外的代码都没有占用更多的空间，因此整段代码的空间复杂度便为 O(n)。

常见的空间复杂度为 O(1) 、 O(n) 、O(n²)，像 O(logn) 和 O(nlogn) 的平时是比较少见的。

六、最好、最坏情况时间复杂度

试想一个有 n 个元素的数组，我们要在这个数组中找到元素 x 的位置

// n 表示数组 array 的长度
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

按照我们之前的说法，很容易就能看出这段代码的时间复杂度为 O(n)，但是我们在数组中查找元素时，并不需要把整个数组全部遍历一遍，我们姚找的那个元素可能出现在数组的任意位置。假如元素 x 在数组的第一个位置，那么时间复杂度就是 O(1)，若是在数组的最后一位，那么时间复杂度就为 O(n)。因此不同情况下，这段代码的时间复杂度是不一样的，所以我们引入两个概念：「最好情况时间复杂度」和 「最坏情况时间复杂度」 。

按照刚才的情况，在最理想的情况下，要查找的元素正好是数组的第一个元素，这时对应的时间复杂度就是最好情况时间复杂度。同理，在最糟糕的情况下，也就是元素不在数组中或者刚好在数组最后一位，这时的时间复杂度就是最坏情况时间复杂度。

七、平均情况时间复杂度

最好和最坏情况时间复杂度都是在极端情况下的发生的，为了更好的表示平均情况下的复杂度，我们就需要引入 「平均情况时间复杂度」。

在刚才查找元素 x 的过程中，共有 n+1 种情况：在数组 0 ~ n-1 位置中和不在数组中，把每种情况下查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，

得到最后结果为 O(n)。
很多时候我们并不用区分这最好、最坏、平均这三个复杂度，只需使用一个复杂度就可以满足需求。只有同一块代码在不同的情况下，时间复杂度有量级的差距的时候才会用这三种表示方法来区分。

八、均摊时间复杂度

在平均情况时间复杂度的基础上引入一种更简单的分析方法：「摊还分析法」，通过摊还分析得到的时间复杂度，就叫 「均摊时间复杂度」。
用一个例子来使用摊还分析法去分析算法的均摊时间复杂度：

// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;

void insert(int val) {
   if (count == array.length) {
      int sum = 0;
      for (int i = 0; i < array.length; ++i) {
         sum = sum + array[i];
      }
      array[0] = sum;
      count = 1;
   }

   array[count] = val;
   ++count;
}

这是一段实现往数组中插入数据的代码，一开始往数组中插入数据，当数组中空间满了之后，会执行一次 for 循环，将数组里的元素加起来并清空数组，并将数组的和放在数组中的第一个位置。分析之后可以知道每执行 n-1 次 O(1)的插入之后都会执行一次 O(n) 的数据插入。

如果我们把耗时多的那次操作，即数组空间满了之后的 O(n) 操作，均摊到 n-1 次耗时少的操作上，均摊下来，这一组连续插入操作的均摊时间复杂度就是 O(1) 。这就是均摊分析的大致思路。

思考

分析下面代码的最好、最坏、平均/均摊时间复杂度：

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}

解答：

当i < len时, 即 i = 0,1,2,…,n-1的时候，for循环不走，所以这n次的时间复杂度都是O(1);
当i >= len时, 即 i = n的时候，for循环进行数组的copy，所以只有这1次的时间复杂度是O(n);
由此可知:
该算法的最好情况时间复杂度为 O(1)；最坏情况时间复杂度为 O(n)。
平均情况时间复杂度：
第一种计算方式: (1+1+…+1+n)/(n+1) = 2n/(n+1) 【注: 式子中1+1+…+1中有n个1】,所以平均复杂度为O(1);
第二种计算方式(加权平均法，又称期望): 1(1/n+1)+1(1/n+1)+…+1(1/n+1)+n(1/(n+1))=1，所以加权平均时间复杂度为O(1);
第三种计算方式(均摊时间复杂度): 前n个操作复杂度都是O(1)，第n+1次操作的复杂度是O(n)，所以把最后一次的复杂度分摊到前n次上，那么均摊下来每次操作的复杂度为O(1)