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

发表于

什么是复杂度分析

  数据结构和算法本身解决的是如何让代码运行的更快，更省存储空间的问题。因此需要从执行时间和占用存储空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模增长的关系。

为什么进行要复杂度分析

  1. 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
  2. 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

如何进行复杂度分析

大 O 复杂度表示法

通过分析如下代码了解大 O 复杂度表示法

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;
}

  假设每行代码执行的时间都一样，为 unit_time。第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n × unit_time 的执行时间，所以这段代码总的执行时间 T(n) = (2n + 2) × unit_time。

1
2
3
4
5
6
7
8
9
10
11
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;
    }
  }
}

  再分析上述代码，第 2、3、4 行代码，每行都需要 1 个 unit_time 的执行时间，第 5、6 行代码循环执行了 n 遍，需要 2n × unit_time 的执行时间，第 7、8 行代码循环执行了 n2 遍，所以需要 2n2 × unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n2 + 2n + 3) × unit_time。

  通过以上两段代码分析可知，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。用 T(n) = O(f(n)) 来表示，其中，T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和，因为这是一个公式，所以用 f(n) 来表示。公式中的 O 表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

  所以，第一个例子中的 T(n) = O(2n + 2)，第二个例子中的 T(n) = O(2n2 + 2n + 3)。这就是大 O 时间复杂度表示法。大 O 时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

  当 n 很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n) 和 T(n) = O(n2)。

复杂度分析

  1. 单段代码看高频：比如循环。
  2. 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
  3. 嵌套代码取乘积：比如递归、多重循环等。
  4. 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

复杂度分析四个重要的概念

  同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入以下四个概念。

  1. 最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
  2. 最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
  3. 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
  4. 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

常见的复杂度实例

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括：O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n2)（平方阶）、O(n3)（立方阶）
非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括：O(2n)（指数阶）、O(n!)（阶乘阶）