算法的复杂度与 Master 定理

平时设计或者阅读一个算法的时候，必然会提到算法的复杂度（包括时间复杂度和空间复杂度）。比如我们说一个二分查找算法的平均时间复杂度为 O(log n)，快速排序可能是 O(n log n)。那这里的 O 是什么意思？这样的表达是否准确呢？

今天来复习一下与算法复杂度相关的知识：函数渐进阶，记号 O、Ω、θ和 o；Master 定理。

先插一句，在算法复杂度分析中，log 通常表示以 2 为底的对数。

算法复杂度（算法复杂性）是用来衡量算法运行所需要的计算机资源（时间、空间）的量。通常我们利用渐进性态来描述算法的复杂度。

用 n 表示问题的规模，T(n) 表示某个给定算法的复杂度。所谓渐进性态就是令 n→∞ 时，T(n) 中增长最快的那部分。严格的定义是：如果存在 $\widetilde{T}(n)$，当 n→∞ 时，有

就说 $\widetilde{T}(n)$ 是 T(n) 当 n→∞ 时的渐进性态。

比如 T(n) = 2 * n ^ 2 + n log n + 3，那么显然它的渐进性态是 2 * n ^ 2，因为当 n→∞ 时，后两项的增长速度要慢的多，可以忽略掉。引入渐进性态是为了简化算法复杂度的表达式，只考虑其中的主要因素。当比较两个算法复杂度的时候，如果他们的渐进复杂度的阶不相同，那只需要比较彼此的阶（忽略常数系数）就可以了。

总之，分析算法复杂度的时候，并不用严格演算出一个具体的公式，而是只需要分析当问题规模充分大的时候，复杂度在渐进意义下的阶。记号 O、Ω、θ和 o 可以帮助我们了解函数渐进阶的大小。

假设有两个函数 f(n) 和 g(n)，都是定义在正整数集上的正函数。上述四个记号的含义分别是：

• f(n) = O(g(n))：$\exists c>0,n_0\in\mathbb{N},\forall n\geq n_0,f(n)\leq c g(n)$；f 的阶 不高于 g 的阶。
• f(n) = Ω(g(n))：$\exists c>0,n_0\in\mathbb{N},\forall n\geq n_0,f(n)\geq c g(n)$；f 的阶 不低于 g 的阶。
• f(n) = θ(g(n))：$\iff f(n)=O(g(n))\&\&f(n)=\Omega(g(n))$；f 的阶 等于 g 的阶。
• f(n) = o(g(n))：$\forall\varepsilon > 0,\exists n_0\in \mathbb{N},\forall n\geq n_0,f(n)/g(n) < \varepsilon$；f 的阶 低于 g 的阶。

可见，记号 O 给出了函数 f(n) 在渐进意义下的上界（但不一定是最小的），相反，记号Ω给出的是下界（不一定是最大的）。如果上界与下界相同，表示 f(n) 和 g(n) 在渐进意义下是同阶的（θ），亦即复杂度一样。

列举一些常见的函数之间的渐进阶的关系：

• $\log n!=\Theta(n\log n)$
• $\log n^2=\Theta(\log n)$
• $\log n^2=O(\sqrt n)$
• $n=\Omega(\log^2n)$
• $\log^2n=\Omega(\log n)$
• $2^n=\Omega(n^2)$
• $2^n=O(3^n)$
• $n!=o(n^n)$
• $2^n=o(n!)$

有些人可能会把这几个记号跟算法的最坏、最好、平均情况复杂度混淆，它们有区别，也有一定的联系。

即使问题的规模相同，随着输入数据本身属性的不同，算法的处理时间也可能会不同。于是就有了最坏情况、最好情况和平均情况下算法复杂度的区别。它们从不同的角度反映了算法的效率，各有用处，也各有局限。

有时候也可以利用最坏情况、最好情况下算法复杂度来粗略地估计算法的性能。比如某个算法在最坏情况下时间复杂度为θ(n ^ 2)，最好情况下为θ(n)，那这个算法的复杂度一定是 O(n ^ 2)、Ω(n) 的。也就是说 n ^ 2 是该算法复杂度的上界，n 是其下界。

接下来看看 Master 定理。

有些算法在处理一个较大规模的问题时，往往会把问题拆分成几个子问题，对其中的一个或多个问题递归地处理，并在分治之前或之后进行一些预处理、汇总处理。这时候我们可以得到关于这个算法复杂度的一个递推方程，求解此方程便能得到算法的复杂度。其中很常见的一种递推方程就是这样的：

设常数 a >= 1，b > 1，f(n) 为函数，T(n) 为非负整数，T(n) = a T(n / b) + f(n)，则有：

1. 若 $f(n)=O(n^{\log_b a-\varepsilon}),\varepsilon > 0$，那么 $T(n)=\Theta(n^{\log_b a})$。
2. 若 $f(n)=\Theta(n^{\log_b a})$，那么 $T(n)=\Theta(n^{\log_b a}\log n)$。
3. 若 $f(n)=\Omega(n^{\log_b a+\varepsilon}),\varepsilon > 0$，并且对于某个常数 c < 1 和充分大的 n 有 $a f(n/b)\leq c f(n)$，那么 $T(n)=\Theta(f(n))$。

比如常见的二分查找算法，时间复杂度的递推方程为 T(n) = T(n / 2) + θ(1)，显然有 $n^{\log_b a}=n^0=\Theta(1)$，满足 Master 定理第二条，可以得到其时间复杂度为 T(n) = θ(log n)。

再看一个例子，T(n) = 9 T(n / 3) + n，可知 $n^{\log_b a}=n^2$，令ε取 1，显然满足 Master 定理第一条，可以得到 T(n) = θ(n ^ 2)。

来一个稍微复杂一点儿例子，T(n) = 3 T(n / 4) + n log n。$n^{\log_b a}=O(n^{0.793})$，取ε = 0.2，显然当 c = 3 / 4 时，对于充分大的 n 可以满足 a * f(n / b) = 3 * (n / 4) * log(n / 4) <= (3 / 4) * n * log n = c * f(n)，符合 Master 定理第三条，因此求得 T(n) = θ(n log n)。

运用 Master 定理的时候，有一点一定要 特别注意 ，就是第一条和第三条中的ε必须 大于零 。如果无法找到大于零的ε，就不能使用这两条规则。

举个例子，T(n) = 2 T(n / 2) + n log n。可知 $n^{\log_b a}=n^1$，而 f(n) = n log n，显然不满足 Master 定理第二条。但对于第一条和第三条，也无法找到大于零的ε使得 $n \log n=O(n^{1-\varepsilon})$ 或者 $n \log n=\Omega(n^{1+\varepsilon})$，因此不能用 Master 定理求解，只能寻求别的方式求解。比如可以利用递归树求出该算法的复杂度为 $T(n)=O(n \log^2{n})$。简单的说一下计算过程：

递归树的建立过程，就像是模拟算法的递推过程。树根对应的是输入的规模为 n 的问题，在递归处理子问题之外，还需要 n log n 的处理时间。然后根据递推公式给根节点添加子节点，每个子节点对应一个子问题。这里需要两个子节点，每个节点处理规模为 n / 2 的问题，分别需要 (n / 2) * log(n / 2) 的时间。因此在第二层一共需要 n * (log n - 1) 的时间。第三层节点就是将第二层的两个节点继续分裂开，得到四个各需要 (n / 4) * log(n / 4) 时间的节点，总的时间消耗为 n * (log n - 2)。依此类推，第 k（设树根为 k = 0）层有 2 ^ k 的节点，总的时间为 n * (log n - k)。而且可以知道，这棵树总共有 log n 层（最后一层每个节点只处理规模为 1 的子问题，无须再分治）。最后将每一层消耗的时间累加起来，得到：