Spiga

用Go撸数据结构（一）：复杂度分析

2020-05-23 15:33:44

最近一直在学习Go语言，因为工作中并没有用到Go，为了不让学到的知识点很快忘掉，我打算用Go语言来撸一遍基本的算法，巩固一下Go语法，也温习一下算法基础。今天是这个系列的第一篇，我们来谈谈什么是复杂度分析。

其实，只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而且认为复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

大 O 复杂度表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

这里有段非常简单的代码，求 1,2,3…n 的累加和。现在，我就带你一块来估算一下这段代码的执行时间。

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

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？

第 2 行代码分别需要 1 个 unit_time 的执行时间，第 3、4行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+1)*unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

按照这个分析思路，我们再来看这段代码。

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

我们依旧假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢？

第 2 行代码，每行都需要 1 个 unit_time 的执行时间，第 3 行代码循环执行了 n 遍，需要 n * unit_time 的执行时间，第 4、5 行代码循环执行了 n​2​遍， 2n​2​ * unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n​2​+n+1)*unit_time。

尽管我们不知道 unit_time 的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

我们可以把这个规律总结成一个公式。注意，大 O 就要登场了！

我来具体解释一下这个公式。其中，T(n) 我们已经讲过了，它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

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

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

时间复杂度分析

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

几种常见时间复杂度实例分析

O(1)

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

O(logn)、O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。我通过一个例子来说明一下。

i := 1
for i <= n {
	i = i * 2
}
return i

根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了。x=log​2​n，所以，这段代码的时间复杂度就是 O(log​2​n)。
现在，我把代码稍微改下，你再看看，这段代码的时间复杂度是多少？

i := 1
for i <= n {
	i = i * 3
}
return i

根据我刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为 O(log3n)。
实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？
我们知道，对数之间是可以互相转换的，log3n 就等于 log​3​2 * log​2​n，所以 O(log​3​n) = O(C * log2n)，其中 C=log​3​2 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log​2​n) 就等于 O(log​3​n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
如果你理解了前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

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

我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度由两个数据的规模来决定。老规矩，先看代码！

func cal(n int, m int) int {
	sum_1 := 0
	for i := 0; i < m; i++ {
		sum_1 = sum_1 + i
	}

	sum_2 := 0
	for j := 0; j < n; j++ {
		sum_2 = sum_2 + j
	}
	return sum_1 + sum_2
}

从代码中可以看出，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))。

空间复杂度分析

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

我还是拿具体的例子来给说明

func print(n int) {
	var a = make([]int, n, n)
	for i := 0; i < n; i++ {
		a[i] = i * i
	}

	for i := n - 1; i >= 0; i-- {
		fmt.Println(a[i])
	}
}

跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型切片，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。

我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握这些内容已经足够了。

复杂度分析的4个概念

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

为什么要引入这4个概念？

  1. 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
  2. 代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

如何分析平均、均摊时间复杂度？

  1. 平均时间复杂度
    代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
  2. 均摊时间复杂度
    两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。