算法分析

2022-06-29 本文已影响0人 Sun东辉

在《为什么要学习算法》中，我们讨论了什么是算法分析，以及为什么要进行算法分析，今天，回过头来再看其中内容，觉得仍需要对算法分析的重要性进行强调，再次，引用 Linux 内核核心开发者 Robert Love 在 Quora 上的回答：“数据结构与算法的良好基础不是对每个数据结构都知道细节怎么实现，都背下来大 O 复杂度和摊销复杂度，当然知道这些非常好，只是你在工作中很少用到它们，你的职业生涯里几乎不可能让你实现一个红黑树和节点删除算法。但是，你必须知道什么时候 BST(二叉排序树)对于一个问题是个有效的解法”，这句话正是说明了算法分析的重要性，换而言之，整个算法学习的精髓正是算法分析，掌握了算法分析，再学习数据结构和算法，就会有醍醐灌顶的效果。

算法分析是科学方法吗？

在使用计算机解决困难问题或是处理大量数据时，不可避免的会产生这样的疑问：我的程序会运行多长时间？为什么我的程序耗尽了所有内存？

这样的问题虽然无法准确回答，但是基于所使用计算机的性能、被处理的数据的性质和完成任务所使用的程序（程序实现的算法），我们可以大致分析出相对准确的答案。分析过程的基础就是科学方法，它是科学家们为获取自然界知识所使用的一系列为大家所认同的方法，对于研究计算机程序的运行时间同样有效。科学方法的过程大致为：

细致地观察真实世界的特点，通常还要有精确的测量；
根据观察结果提出假设模型；
根据模型预测未来的事件；
继续观察并核实预测的准确性；
如此反复直到确认预测和观察一致。

科学方法的一条关键原则是我们所设计的实验必须是可重现的，这样他人也可以自己验证假设的真实性。所有的假设也必须是可证伪的，这样我们才能确认某个假设是错误的，需要修正的。正如爱因斯坦的一句名言所说：“再多的实验也不一定能够证明我是对的，但只需要一个实验就能证明我是错的。”我们永远也没法知道某个假设是否绝对正确，我们只能验证它和我们的观察的一致性。

建立数学模型

在计算机科学的早期，D. E. Knuth 认为，尽管有许多复杂的因素影响着我们对程序的运行时间的理解，原则上我们仍然可能构造出一个数学模型来描述任意程序的运行时间。在 Knuth 看来，一个程序运行的总时间主要和两点有关：

执行每条语句的耗时；
执行每条语句的频率。

前者取决于计算机、Java 编译器和操作系统，后者取决于程序本身和输入。如果对于程序的所有部分我们都知道了这些性质，可以将它们相乘并将程序中所有指令的成本相加得到总运行时间。

关于执行每条语句的耗时，这里暂不做讨论，关于每条语句的频率，我们可以使用数学表达式来归纳总结，这不失为一种好的方法，但是，数学表达式可能会复杂冗长，不利于理解，而且，虽然有时我们能够确定一个算法的精确运行时间，但是通常并不值得花精力去这么做，只需要近似的估计程序的运行时间即可。进一步的思考，当输入规模足够大时，运行时间其实只和增长量级相关，实际上，我们要研究的是算法的渐近效率，即当输入规模无限增加时，算法的运行时间如何随输入规模的变大而增加。这就意味着，我们需要将程序和它实现的算法隔离开来，分析算法增长的数量级。

渐近分析（asymptotic analysis、asymptotics）

渐近分析是一种描述函数在极限附近的行为的方法。渐近分析方法在多个科学领域得到应用。

在统计学中，渐近理论提供了限制近似概率分布的样本统计，如似然比统计量和所述期望值中的偏差。
在计算机科学中，算法分析考虑给定算法在输入非常大的数据集时的性能。
在实体系统中，渐近理论用于分析当实体系统的规模变得非常大时的行为。

渐近分析也是探索现实世界现象的数学建模中出现的常微分方程和偏微分方程的关键工具。

在进行渐近分析时，我们还需要知道一些概念：

渐近等价

给定关于自然数 n 的复函数 $f$ 和 $g$ ，命题 $f(n)\sim g(n)(n \rightarrow \infty)$ 用小 $o$ 表示为：

$f(n)\;=\;g(n)+o(g(n))\;(n\;\rightarrow\;\infty)$

也等价于：

$f(n)\;=\;(1+o(1))g(n)\;(n\;\rightarrow\;\infty)$

这说明，对所有正常数 $\varepsilon$ ，存在常量 N，使得对于所有的 $n \geq N$ 有：

$\left|f(n)-g(n)\right|\;\leq\varepsilon\left|g(n)\right|$

当 $g(n)$ 不是 0 或者趋于无穷大时，该命题可等价记作：

$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=1$

渐近等价是一个关于 n 的函数的集合上的等价关系。非正式地，函数 $f$ 的等价类包含所有在极限情况下近似等于 $f$ 的函数 $g$ 。

渐近展开

函数 $f(x)$ 的渐近展开是它的一种级数展开。这种展开的部分和未必收敛，但每一个部分和都表示 $f(x)$ 的一个渐近表达式。

渐近记号

在算法分析中，我们通常使用渐近记号来刻画算法的运行时间，但它也可以用于刻画算法的其他方面的函数，比如，算法所占用的空间，甚至，可以用于和算法没有任何关系的函数。

$\Theta$ 记号

定义：对于一个给定的函数 $g(n)$ ，用 $\Theta(g(n))$ 来表示以下函数的集合：

$\Theta(g(n))$ = { $f(n)$ :存在正常量 $c_1、c_2$ 和 $n_0$ 使得对所有 $n \geq n_0$ ，有 $0 \leq c_1g(n)\leq f(n)\leq c_2g(n)$ }。（其中，”:”代表“使得”）通俗的说， $\Theta$ 记号渐近地给出一个函数的上界和下界。

解释：对任一个函数 $f(n)$ ，若存在正常数 $c_1$ ， $c_2$ ，使得当 n 足够大时， $f(n)$ 的结果能够满足 $c_1g(n)$ 大于等于 0，且 $f(n)$ 大于等于 $c_1g(n)$ 且小于等于 $c_2g(n)$ ，则 $f(n)$ 属于集合 $\Theta(g(n))$ 。由于 $\Theta(g(n))$ 是一个集合，可以写成 “ $f(n)\in\Theta(g(n))$ ”，表示 $f(n)$ 是 $\Theta(g(n))$ 的成员。不过，通常写成 “ $f(n)=\Theta(g(n))$ ”来表示相同的意思。

上图是 $f(n)$ 与 $g(n)$ 的直观图示，其中 $f(n)$ = $\Theta(g(n))$ 。对于 $n_0$ 及其右边 n 的所有值， $f(n)$ 的值高于 $c_1g(n)$ 且低于 $c_2g(n)$ ，换句话说，对所有的 n≥ $n_0$ ，函数 $f(n)$ 在一个常量因子范围内等于 $g(n)$ 。我们称 $g(n)$ 是 $f(n)$ 的一个渐近紧确界（asymptotically tight bound）。

$\Theta(g(n))$ 的定义需要每个成员 $f(n)\in\Theta(g(n))$ 均是渐近非负，即当 n 足够大时， $f(n)$ 是非负值（渐近正函数则是对所有足够大的 n 均为正的函数）。因此，函数 $g(n)$ 本身必须是渐近非负的，否则集合 $\Theta(g(n))$ 就是空集。

例：证明 $\frac{1}{2}n^2-3n=\Theta(n^2)$ 。

为证明 $\frac{1}{2}n^2-3n=\Theta(n^2)$ 成立，我们需要证明，存在常数 $c_1$ ， $c_2$ ，当 $n\geq n_0$ 时，不等式始终成立。

假设存在常数 $c_1$ ， $c_2$ 和 $n_0$ ，使得当 n≥ $n_0$ 时，满足

$c_1n^2\leq\frac12n^2-3n\leq c_2n^2$

用 $n^2$ 除以上式，得到：

$c_1\leq\frac12-\frac3n\leq c_2$

我们先来看不等式右边，当 $c_2\geq\frac{1}{2}$ 时，对所有的 $n\geq 0$ ，不等式成立。同理，当 $c_1\leq\frac{1}{14}$ 时对所有的 $n\geq7$ ，不等式成立，对 n 取交集，即当 $c_1=\frac{1}{14}$ ， $c_2=\frac{1}{2}$ ， $n_0 = 7$ 时，不等式成立。

将 $c_1$ ， $c_2$ 带入，可以看出，当 $n_0$ 大于 7 时， $\frac{1}{7}\leq\frac12-\frac3n\leq \frac{1}{2}$ 始终成立。因此， $\frac{1}{2}n^2-3n=\Theta(n^2)$ 成立。

O 记号

定义：对于给定函数 g(n)，用 O(g(n))（读作“大 Og(n)”，有时仅读作”Og(n)”）来表示以下函数的集合：

$O(g(n))=\{f(n):存在正常量 c 和 n_0，使得对所有 n \geq n_0，有 0 \leq f(n) \leq cg(n)\}$

通俗的说，当只有一个渐近上界时，用 O 记号来给出函数的一个在常量因子内的上界。

上图是 O 记号的直观图示。对在 $n_0$ 及其右边的所有值 n，函数 $f(n)$ 的值总小于或等于 $cg(n)$ 。我们可以用 $f(n) = O(g(n))$ 来表示函数 $f(n)$ 是集合 $O(g(n))$ 的成员。

使用 O 记号，我们常常可以仅通过检查算法的总体结构来描述算法的运行时间。例如，插入排序算法的双重嵌套循环结构对最坏情况运行时间确定了一个 $O(n^2)$ 的上界：内层循环每次迭代的代价以 $O(1)$ （常量）为上界，下标 i 和 j 均最多为 n，对于 $n^2$ 个 i 和 j 值的关系对，内循环最多执行一次。

从技术上看，称插入排序的运行时间为 $O(n^2)$ 有点儿不合适，因为对给定的 n，实际的运行时间是变化的，依赖于规模为 n 的特定输入。当我们说“运行时间为 $O(n^2)$ ”时，意指存在一个 $O(n^2)$ 的函数 $f(n)$ ，使得对 n 的任意值，不管选择什么特定规模为 n 的输入，其运行时间的上界都是 $f(n)$ 。也就是说最坏情况下，运行时间为 $O(n^2)$ 。

$\Omega$ 记号

定义：对于给定的函数 $g(n)$ ，用 $\Omega(g(n))$ （读作“大 $\Omega g(n)$ ”，有时仅读作“ $\Omega g(n)$ ”）来表示以下函数的集合：

$\Omega(g(n)) =\{f(n):存在正常量 c 和 n_0，使得对所有 n \geq n_0，有 0 \leq cg(n) \leq f(n)\}$

上图是 $\Omega$ 记号的直观图示。对在 $n_0$ 及其右边的所有值 n， $f(n)$ 的值总大于或等于 $cg(n)$ 。

o 记号

定义：对于给定函数 g(n)，用 o(g(n))（读作“小 og(n)”）来表示以下函数的集合：

$o(g(n))=\{f(n):对任意常量 c>0，存在常量 n_0>0，使得对所有 n \geq n_0，有 0 \leq f(n) < cg(n) \}$

我们用 o 记号来表示一个非渐近紧确的上界。可以看出，o 记号与 O 记号的定义类似，主要的区别是在 $f(n)=O(g(n))$ 中，界 $0 \leq f(n) \leq cg(n)$ 对某个常量 $c>0$ 成立，但在 $f(n)=o(g(n))$ 中，界 $0 \leq f(n) < cg(n)$ 对所有常量 $c>0$ 成立。直观上，在 o 记号中，当 n 趋于无穷时，函数 $f(n)$ 相对于 $g(n)$ 来说变得微不足道了，即

$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0$

$\omega$ 记号

定义：对于给定的函数 $g(n)$ ，用 $\omega(g(n))$ （读作“小 $\omega g(n)$ ”）来表示以下函数的集合：

$\omega(g(n))=\{f(n):对任意正常量 c>0，存在常量 n_0>0，使得对所有 n \geq n_0,有 0 \leq cg(n) < f(n)\}$

$\omega$ 记号与 $\Omega$ 记号的关系类似于 o 记号和 O 记号的关系。我们用 $\omega$ 记号来表示一个非渐近紧确的下界。关系 $f(n)=\omega(g(n))$ 蕴含着

$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$

也就是说，如果这个极限存在，那么当 n 趋于无穷时， $f(n)$ 相对于 $g(n)$ 来说变得任意大了。

定理

定理：对任意两个函数 $f(n)$ 和 $g(n)$ ，我们有 $f(n)=\Theta(g(n))$ ，当且仅当 $f(n)=O(g(n))$ 且 $f(n)=\Omega(g(n))$ 。

解释：当称一个算法的运行时间为 $\Omega(g(n))$ 时，我们意指对每个 n 值，不管选择什么特定规模为 n 的输入，只要 n 足够大，对那个输入的运行时间至少是 $g(n)$ 的常量倍。同样的，当称一个算法的运行时间为 $O(n^2)$ 时，我们意指对足够大的 n 值，运行时间至多不会超过 $g(n^2)$ 的常量倍。例如，插入排序的最好情况运行时间为 $\Omega(n)$ ，最坏情况运行时间为 $O(n^2)$ ，

参考文献

《算法导论第三版》
《算法第四版》
维基百科