复杂度分析

在算法入门中，我们已经基本了解了算法的定义，下面我会对如何衡量算法的性能进行更深入地讨论。

1 事前分析

一个算法的性能到底如何，直接执行一下，统计性能数据不就行了嘛！很多情况下，「事后统计」似乎是一个显而易见的答案。

但很多情况下我们无法做这样的的统计，比如我们要对导弹上的算法进行性能测试，一颗导弹的价格可能就高大几十万甚至上亿，导弹上有很多解决不同问题的算法，如果每种算法都要实际测试，会消耗掉大量的资源！

其次，对于每个问题，我们可能先要尝试一些简单的算法，然后逐步去找到最适合的算法。如果不能先对算法进行「事前分析」，那么研发成本将无法接受。

尽管上面的例子有些极端，但如果我们可以很快的分析出 A 算法的性能比 B 算法的性能好，那么我们就无需真正的去执行 B 算法，就直接排除它。快速的排除较差的算法可以节省不少计算资源和时间，从而更快地找到解决问题的最优算法。

2 大 O 表示法

如果真正的比较两个算法的实际性能，可能会是一件比较复杂的问题。比如 A 算法的执行次数是 $2n+3$，B 算法的执行次数是 $n^2 + n + 10$，当 $n \to \infty$ 时，A 算法的主要由 $2n$ 决定，B 算法主要由 $n^2$ 决定，我们只要比较它们的主体部分就可以确定它们的大小关系。

大 O 表示法 是将它们主体的常数项也去掉，然后用 O 和括号包起来，A B 算法分别表示为 $O(n)$ 和 $O(n^2)$，这样我们就更清晰的比较它们。

常见渐近复杂度比较如下：

$$ O(1) < O(log_2{n}) < O(n) < O(nlog_2{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) $$

3 复杂度分析

通常来说，一个好的算法一定是「即快又省」的！快是指它运行的速度快，省是指它占用的存储空间小。

我们通过对时间复杂度和空间复杂度的综合分析，来评判一个算法的好坏！

3.1 时间复杂度

这里的时间是指程序在 CPU 上的运行时间，在没有实际运行的情况下，我们很难估算出这个时间，因此我们用 单次运行时间 * 运行次数 来近似表示，我们又假设单次运行的平均时间是相同的，所以仅仅可以通过估算代码的运行次数估算出大概的运行时间。

n = 10
j = 0
for i in range(n):
    j = i + j
print(j)

我们看上面这段 Python 代码，它的运行次数为 $2+10+1=13$，它用大 O 表示法为 $O(n)$。

3.2 空间复杂度

空间复杂度即是算法在运行中所需要的空间大小。如果原地工作，不使用额外的空间，那么算法的空间复杂度就是 $O(1)$；如果算法需要额外使用与数据长度成简单正比关系，那么空间复杂度就是 $O(n)$。

n = 10
j = 0
sum_list = []
for i in range(n):
    j = i + j
    sum_list.append(j)
print(sum_list)

假设我们需要保存每一步 j 的值，就需要一个大小为 n 的数组，所占空间即为 n，它用大 O 表示法为 $O(n)$。

学会了时间复杂度和空间复杂度，就可以对算法进行事前预估！快去找一些算法试着分析一下吧～

4 参考

• 时间复杂度