复杂度分析

对于算法执行的时间和空间的分析，通过分析可以衡量算法的执行效率。

事后统计法

通过统计、监控得到算法执行的时间和占用的内存大小

局限性

  • 测试结果依赖于测试环境
  • 测试结果受数据规模的影响比较大

大 O 复杂度表示法

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

1
T(n) = O(f(n))

大 O 时间复杂度表示法 表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。

例如：假设每行代码的执行时间是 unitTime 且每行代码的执行时间相同，则下面代码的执行总时间是 $(2n + 2) * unitTime$ 即 $T(n) = O(2n + 2)$，当 n 趋近于无穷大时，则用量级表示即可：$T(n) = O(n)$，如果是双层循环则是：$T(n) = O(n^2)$

1
2
3
4
5
6
7
8
int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

时间复杂度分析

分析方法

  • 关注循环执行次数最多的一段代码
  • 加法法则：总复杂的等于量级最大的那段代码的复杂度
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘机

常见复杂度量级

  • 常量阶 $O(1)$
  • 对数阶 $O(logn)$
  • 线性阶 $O(n)$
  • 线性对数阶 $O(nlogn)$
  • k 次方阶 $O(n^2)$ $O(n^3)$…$O(n^k)$
  • 指数阶 $O(2^n)$
  • 阶乘阶 $O(n!)$

非多项式量级：$O(2^n)$ 和 $O(n!)$，其他的是多项式量级，非多项式量级的算法问题叫做 NP (Non-Deterministic Polynomial)非确定多项式问题

空间复杂度分析

空间复杂度是算法的存储空间与数据规模之间的增长关系，也叫做渐进空间复杂度

复杂度分析补充

最好情况时间复杂度

在理想的情况下执行代码的时间复杂度；例如下面代码的最好情况时间复杂度是：$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
// 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)$

平均情况时间复杂度

将每种情况出现的概率考虑进去，例如上面的代码：要查找的数据出现在数组中和不出现在数组中的概率是$1/2$，出现在 0～n-1 这 n 个位置的概率是 $1/n$，则要查找的数据可能出现在数组中的概率是：$1/2n$，将每种情况发生的情况考虑进去就是，去掉系数常量就是 $O(n)$
$$
1\frac{1}{2n} + 2\frac{1}{2n}+…+n\frac{1}{2n}+n\frac{1}{2}=\frac{n(n+1)}{4n}+\frac{n}{2}=\frac{3n+1}{4}
$$

均摊时间复杂度

对一个数据结构的一组操作中，大部分情况下耗时都很低，个别情况比较高，并且这些操作存在前后连贯的时序关系，可以将这一组操作放在一块儿分析，将高耗时的分摊到其他情况中。