01 复杂度分析

0.1. 数据结构与算法

从广义上讲：

  • 数据结构：一组数据的存储结构。
  • 算法：操作数据的一组方法。

从狭义上讲:

  • 指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。

数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。 因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。

最常用的10个数据结构：

  • 数组
  • 链表
  • 栈
  • 队列
  • 散列表
  • 二叉树
  • 堆
  • 跳表
  • 图
  • Trie树

最常用的10个算法：

  • 递归
  • 排序
  • 二分查找
  • 搜索
  • 哈希算法
  • 贪心算法
  • 分治算法
  • 回溯算法
  • 动态规划
  • 字符串匹配算法

学习数据结构与算法的：

  • 来历
  • 自身特点
  • 适合解决的问题
  • 实际的应用场景

0.2. 分析、统计算法的执行效率和资源消耗

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。

0.2.1. 事后统计法

把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小，这种评估算法执行效率的方法是正确的，但是有很大的局限性。

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是时间、空间复杂度分析方法。

0.2.2. 大O复杂度表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。如下示例，求1...n的累加和：

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

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据->运算->写数据。

尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为unit_time。

在这个假设的基础之上，这段代码的总执行时间是:

  1. 第2、3行代码分别需要1个unit_time的执行时间
  2. 第4、5行代码都运行了n遍，需要的时间是\(2n×unit\_time\)的执行时间
  3. 整段代码总执行时间是\((2n+2)×unit\_time\)

如下示例，两重for循环：

1    func cals(n int) {
2     sum := 0
3     i := 1
4     j := 1
5     for ; i <= n; i++ {
6      j = 1
7      for ; j <= n; j++ {
8       sum = sum + i*j
9      }
10     }
11    }

这段代码的总执行时间T(n)是：

  1. 第 2、3、4 行代码，每行都需要 1 个 unit_time 的执行时间
  2. 第 5、6 行代码循环执行了 n 遍，需要 \(2n × unit\_time\) 的执行时间
  3. 第 7、8 行代码循环执行了 \(n^2\) 遍，所以需要 \(2n^2 × unit\_time\) 的执行时间
  4. 整段代码总的执行时间是\((2n^2+2n+3) × unit\_time\)

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

总结成公式：\(T(n)=O(f(n))\)

  • T(n)：表示代码执行的时间
  • n：表示数据规模的大小
  • f(n)：表示每行代码执行的次数总和
  • O：表示代码的执行时间T(n)与f(n)表达式成正比

所以，第一个例子\(T(n)=O(2n+2)\)，第二个例子\(T(n)=O(2n^2+2n+3)\)。

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐近时间复杂度（asymptotic time complexity），简称时间复杂度。

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

0.2.3. 时间复杂度分析

0.2.3.1. 只关注循环执行次数最多的一段代码

大O复杂度表示法只是表示一种变化趋势。通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级。

所以，在分析一个算法、一段代码的时间复杂度时，只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

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

从时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，都可以忽略掉，因为它本身对增长趋势并没有影响。

总的时间复杂度就等于量级最大的那段代码的时间复杂度。

\[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)))\]

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

\[T1(n)=O(f(n))\]

\[T2(n)=O(g(n))\]

\[T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))\]

把乘法法则看成是嵌套循环。

0.2.3.4. 常见时间复杂度分析

复杂度多项式量级：

  • 常量阶：\(O(1)\)
  • 对数阶：\(O(logn)\)
  • 线性阶：\(O(n)\)
  • 线性对数阶：\(O(nlogn)\)
  • 平方阶：\(O(n^2)\)
  • 立方阶：\(O(n^3)\)
  • k次方阶：\(O(n^k)\)

image

复杂度非多项式量级：

  • 指数阶：\(O(2^n)\)
  • 阶乘阶：\(O(n!)\)

时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

0.2.3.4.1. \(O(1)\)

代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度都记作 O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

0.2.3.4.2. \(O(logn)\)&\(O(nlogn)\)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。

1     i := 1
2     for i <= n {
3      i *= 2
4     }
5    }

第三行代码是循环执行次数最多的，代表整段代码的时间复杂度。

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2，当大于 n 时，循环结束。实际上，变量 i 的取值就是一个等比数列，\(2^0,2^1,...,2^k,...2^x=n\)。只要知道x的值，就知道代码的执行次数。通过\(2^x=n\)求解x得\(x=log2^n\)，所以代码的时间复杂的就是\(O(log2^n)\)。

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为\(O(logn)\)而直接忽略对数的底。因为对数之间可以相互转换，即\(log3^n=log3^2×2log2^n\),所以\(O(log3n)=o(C×log2^n)\)，其中\(C=log3^2\)是一个常量，可以忽略。

根据乘法法则，如果一段代码时间复杂度是\(O(logn)\)，那么它循环执行n遍的时间复杂度就是\(O(nlogn)\)。

0.2.3.4.3. \(O(m+n)\)&\(O(m*n)\)

另一种时间复杂度，由两个数据的规模来决定。

1    func cal(m, n int) int {
2     sum1 := 0
3     i := 1
4     for ; i < m; i++ {
5      sum1 += i
6     }
7
8     sum2 := 0
9     j := 1
10     for ; i < n; j++ {
11      sum2 += j
12     }
13
14     return sum1 + sum2
15    }

m 和 n 是表示两个数据规模，无法事先评估 m 和 n 谁的量级大，所以在表示复杂度时，不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 \(O(m+n)\)。

针对这种情况，原来的加法法则就不正确了，需要将加法规则改为：\(T1(m)+T2(n)=O(f(m)+g(n))\)。但是乘法法则继续有效：\(T1(m)×T2(n)=O(f(m)×f(n))\)。

0.2.4. 空间复杂度分析

空间复杂度全称就是渐近空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

1    func print(n int) {
2     i := 0
3     a := make([]int, n)
4     for ; i < n; i++ {
5      a[i] = i * i
6     }
7
8     for i = n - 1; i >= 0; i++ {
9      print(a[i])
10     }
11    }
  1. 第 2 行代码中，申请一个空间存储变量 i，它是常量阶跟数据规模 n 无关，可以忽略
  2. 第 3 行申请了一个大小为 n 的 int 类型切片
  3. 其他代码都没有占用空间，所以整段代码的空间复杂度是\(O(n)\)

常见的空间复杂度就是 \(O(1)\)、\(O(n)\)、\(O(n^2)\)，像 \(O(logn)\)、\(O(nlogn)\) 这样的对数阶复杂度平时都用不到。

0.3. 最好、最坏情况时间复杂度

// n 代表数组array的长度
func find(array []int, n, x int) int {
 i := 0
 pos := -1
 for ; i < n; i++ {
  if array[i] == x {
   pos = i
  }
 }
 return pos
}
// 在一个无序的数组（array）中，查找变量 x 出现的位置。如果没有找到，就返回 -1
// 时间复杂度O(n)

在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，因为有可能中途找到就可以提前结束循环了，上面代码写得不够高效。可以这样优化一下这段查找代码。

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

那么问题来了，优化完之后，这段代码的时间复杂度还是 \(O(n)\) 吗？

要查找的变量 x 可能出现在数组的任意位置，不同的情况下，这段代码的时间复杂度是不一样的。

  • 如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 \(O(1)\)。
  • 如果数组中不存在变量 x，那就需要把整个数组都遍历一遍，时间复杂度就成了 \(O(n)\)。
  • 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
  • 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。

0.4. 平均情况时间复杂度

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，引入平均情况时间复杂度，简称为平均时间复杂度。

使用上面的查找X的例子，有 n+1 种情况：n种情况，在数组的 \(0～n-1\) 位置中以及1种情况，不在数组中。把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

image

省略掉系数、低阶、常量，把这个公式简化后，得到的平均时间复杂度就是 \(O(n)\)。

上述计算过程存在一些问题，忽略了各种情况出现的概率。

  • 假设在数组中与不在数组中的概率都为 \(\frac{1}{2}\)
  • 要查找的数据出现在 \(0～n-1\) 这 n 个位置的概率也是一样的，为 \(\frac{1}{n}\)

根据概率乘法法则，要查找的数据出现在 \(0～n-1\) 中任意位置的概率就是 \(\frac{1}{2n}\)。

如果把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：

image

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

引入概率之后，前面那段代码的加权平均值为 \(\frac{3n+1}{4}\)\(/4\)。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 \(O(n)\)。

实际上，在大多数情况下，并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候，使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，才会使用这三种复杂度表示法来区分。

0.5. 均摊时间复杂度

平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。

var array = make([]int, n)
var count = 0

func insert(val int) {
 if count == len(array) {
  sum := 0
  for i := 0; i < len(array); i++ {
   sum += array[i]
  }
  array[0] = sum
  count = 1
 }
 array[count] = val
 count++
}

这段代码实现了一个往数组中插入数据的功能。

  1. 当数组满了之后，也就是代码中的 count == len(array) 时，
  2. 用 for 循环遍历数组求和，并清空数组，
  3. 将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。
  4. 如果数组一开始就有空闲空间，则直接将数据插入数组。

时间复杂度：

  • base case：\(O(1)\)
  • worst case： \(O(n)\)
  • average case：\(O(1)\)，绝大部分情况都是\(O(1)\)，只有一种情况是\(O(n)\)，发生的概率都是\(\frac{1}{n+1}\)

分析上面的find和这里的insert函数，发现：

  • 区别1：find函数在极端情况下，复杂度才为 \(O(1)\)。但insert在大部分情况下，时间复杂度都为\(O(1)\)
  • 区别2：insert 函数，\(O(1)\) 时间复杂度的插入和 \(O(n)\) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 \(O(n)\) 插入之后，紧跟着 n-1 个 \(O(1)\) 的插入操作，循环往复。

针对这样一种特殊场景的复杂度分析，并不需要找出所有的输入情况及相应的发生概率，然后再计算加权平均值。引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度叫均摊时间复杂度。

以上面insert函数为例，每一次 \(O(n)\) 的插入操作，都会跟着 n-1 次 \(O(1)\) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 \(O(1)\)。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度。

上次修改: 18 June 2020