算法/数学背景

顶部，章节：1，2，3，4，5，6，7，8，9，A

在我们开始学习算法技术之前，我们将先绕道介绍一些必要的数学工具。首先，我们将介绍一些将在本书后面使用的术语的数学定义。通过扩展你的数学词汇，你可以更加精确地描述问题或更容易地表达问题。然后，我们将介绍分析算法运行时间的方法。在本专著中，我们将在介绍每个主要算法之后给出其运行时间的分析以及其正确性的证明。

渐进符号

除了正确性之外，另一个重要的算法特征是其时间和内存消耗。时间和内存都是宝贵的资源，它们在使用方式上存在显著差异（即使两者都充足）。

如何衡量资源消耗？一种方法是创建一个函数，用输入的一些特征来描述资源的使用情况。一个常用的输入数据集特征是其大小。例如，假设一个算法以一个包含 $n$ 个整数的数组作为输入。我们可以将这个算法所需的时间描述为一个以 $n$ 为变量的函数 $f$。例如，我们可以写成

$f(n)=n^{2}+3n+14$

其中 $f(n)$ 是某个时间单位（在本讨论中，主要关注的是时间，但我们也可以用它来描述内存消耗）。时间单位很少是实际的秒数，因为这会取决于机器本身、它运行的系统以及系统负载。相反，时间单位通常用执行某些基本操作的次数来表示。例如，我们可能关心的一些基本操作包括：所需的加法或乘法次数；元素比较次数；内存位置交换次数；或执行的机器指令数量。通常，我们可能会简单地将这些执行的基本操作称为执行的步骤。

这是否是确定算法资源消耗的好方法？是也不是。当两种不同的算法在时间消耗上相似时，精确的函数可能有助于确定在给定条件下哪个算法更快。但在许多情况下，计算执行所需操作确切数量的解析描述要么很困难，要么根本不可能，尤其是在算法根据其输入的值有条件地执行操作时。相反，真正重要的是不是完成函数所需的精确时间，而是资源消耗根据其输入变化的程度。具体而言，考虑以下两个函数，它们分别代表每个输入数据集大小所需的计算时间

$f(n)=n^{3}-12n^{2}+20n+110$

$g(n)=n^{3}+n^{2}+5n+5$

它们看起来很不同，但它们的行为如何？让我们看看函数的一些图像（$f(n)$ 为红色，$g(n)$ 为蓝色）

f 和 g 在 0 到 5 范围内的图像	f 和 g 在 0 到 15 范围内的图像
f 和 g 在 0 到 100 范围内的图像	f 和 g 在 0 到 1000 范围内的图像

在第一个非常有限的图像中，曲线看起来有些不同。在第二个图像中，它们开始以某种方式呈现相同的趋势，在第三个图像中，它们之间只有很小的差异，最后它们几乎完全相同。实际上，它们逼近 $n^{3}$，即主导项。当 n 变大时，其他项与 n³ 相比变得微不足道。

正如你所看到的，修改多项式时间算法的低阶系数并没有太大帮助。真正重要的是最高阶系数。这就是为什么我们采用了这种符号来进行这种分析。我们说

$f(n)=n^{3}-12n^{2}+20n+110=O(n^{3})$

我们忽略了低阶项。我们可以说

$O(\log {n})\leq O({\sqrt {n}})\leq O(n)\leq O(n\log {n})\leq O(n^{2})\leq O(n^{3})\leq O(2^{n})$

这为我们提供了一种更便捷的方式来比较不同的算法。对$n$个元素进行插入排序需要$O(n^{2})$数量级的步骤。归并排序的排序步骤为$O(n\log {n})$。因此，一旦输入数据集足够大，归并排序就会比插入排序更快。

一般来说，我们写

$f(n)=O(g(n))$

当

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n).$

也就是说，$f(n)=O(g(n))$成立当且仅当存在一些常数$c$和$n_{0}$，使得对于所有$n>n_{0}$，$f(n)$为正且小于等于$cg(n)$。

注意，此符号中使用的等号描述了$f(n)$和$g(n)$之间的关系，而不是反映真正的相等性。鉴于此，有些人用集合来定义大O符号，指出

$f(n)\in O(g(n))$

当

$f(n)\in \{f(n):\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n)\}.$

大O符号只是一个上界；这两个都是真的

$n^{3}=O(n^{4})$

$n^{4}=O(n^{4})$

如果我们将等号用作等式，我们会得到非常奇怪的结果，例如

$n^{3}=n^{4}$

这显然是胡说八道。这就是为什么集合定义很方便。你可以通过将等号视为单向等式来避免这些情况，即

$n^{3}=O(n^{4})$

并不意味着

$O(n^{4})=n^{3}$

始终将 O 保持在右侧。

大 Omega

有时，我们想要更多地了解某个函数行为的上界。大 Omega 提供了下界。一般来说，我们说

$f(n)=\Omega (g(n))$

当

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)\leq f(n).$

即 $f(n)=\Omega (g(n))$ 当且仅当存在常数 c 和 n₀ 使得对于所有 n>n₀ f(n) 为正且大于或等于 cg(n)。

所以，例如，我们可以说

$n^{2}-2n=\Omega (n^{2})$，(c=1/2, n₀=4) 或

$n^{2}-2n=\Omega (n)$，(c=1, n₀=3)，

但声称

$n^{2}-2n=\Omega (n^{3}).$

大 Theta

当给定函数同时为 O(g(n)) 和 Ω(g(n)) 时，我们说它是 Θ(g(n))，并且我们对该函数有了严格的界限。函数 f(n) 为 Θ(g(n)) 时

$\exists c_{1}>0,\exists c_{2}>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c_{1}\cdot g(n)\leq f(n)\leq c_{2}\cdot g(n),$

但大多数时候，当我们试图证明给定的 $f(n)=\Theta (g(n))$ 时，我们并不使用这个定义，而是证明它同时是 O(g(n)) 和 Ω(g(n))。

小 O 和 Omega

当渐近界限不紧密时，我们可以用 $f(n)=o(g(n))$ 或 $f(n)=\omega (g(n)).$ 来表达。定义如下：

f(n) 是 o(g(n)) 当且仅当 $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)<c\cdot g(n)$，并且

f(n) 是 ω(g(n)) 当且仅当 $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)<f(n).$

请注意，当对于 g 的任何系数，g 最终都大于 f 时，函数 f 属于 o(g(n))；而对于 O(g(n))，只需要存在一个系数，使得 g 最终至少与 f 一样大。

大O 多变量

给定两个参数的函数 $f(n,m)$ 和 $g(n,m)$，

$f(n,m)=O(g(n,m))$ 当且仅当 $\exists c>0,\exists n_{0}>0,\exists m_{0}>0,\forall n\geq n_{0},\forall m\geq m_{0}:0\leq f(n,m)\leq c\cdot g(n,m)$。

例如，$5n+3m=O(n+m)$，以及 $n+10m+3nm=O(nm)$。

算法分析：求解递归方程

合并排序 n 个元素：$T(n)=2*T(n/2)+c(n)$ 这描述了合并排序的一次迭代：问题空间 $n$ 被缩减成两个一半 ($2*T(n/2)$)，然后在所有递归调用结束时合并在一起 ($c(n)$)。这个符号系统是算法分析的精髓，所以要习惯它。

有一些定理可以用来估计一个函数的 Big Oh 时间，前提是它的递归方程符合某种模式。

替换法

对你的方程的 Big Oh 时间做一个猜测。然后使用归纳法证明这个猜测是正确的。

画树和表

这实际上只是一种获得明智猜测的方法。你仍然必须回到替换法来证明 Big Oh 时间。

主定理

考虑一个递归方程，它符合以下公式

$T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$

对于 a ≥ 1, b > 1 和 k ≥ 0。这里，a 是每次函数调用产生的递归调用次数，n 是输入大小，b 是每次输入缩小多少，k 是每次函数调用（除了基本情况）执行的操作的多项式阶数。例如，在后面介绍的合并排序算法中，我们有

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

因为每次非基本情况迭代都会调用两个子问题，并且数组的大小每次都会减半。最后的 $O(n)$ 是这个分治算法的“征服”部分：将两个递归调用的结果合并成最终结果需要线性时间。

将 T 的递归调用视为形成一棵树，有三种可能的情况来确定算法的大部分时间都花在哪里（这里“大部分”指的是它的渐进行为）

1. 这棵树可能是头重脚轻的，大部分时间花在接近根部的初始调用上；
2. 这棵树可能有一个稳定状态，时间均匀分布；或者
3. 这棵树可能头轻脚重，大部分时间花在接近叶子的调用上

根据树处于这三种状态中的哪一种，T 将有不同的复杂度

主定理

假设给定 $T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$ 对于 a ≥ 1, b > 1 和 k ≥ 0

• 如果 $a<b^{k}$，那么 $T(n)=O(n^{k})\$ （头重脚轻）
• 如果 $a=b^{k}$，则 $T(n)=O(n^{k}\cdot \log n)$（稳定状态）
• 如果 $a>b^{k}$，则 $T(n)=O(n^{\log _{b}a})$（底部沉重）

对于上面提到的归并排序示例，其中

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

我们有

$a=2,b=2,k=1\implies b^{k}=2$

因此，$a=b^{k}$，所以这也处于“稳定状态”：根据主定理，归并排序的复杂度因此为

$T(n)=O(n^{1}\log n)=O(n\log n)$.

均摊分析

（从图的邻接表表示开始，并显示两个嵌套的for循环：一个用于每个节点n，另一个嵌套在该循环中，用于每个边e。如果有n个节点和m个边，这可能导致你说循环需要O(nm)时间。但是，只有在一次循环中，内部循环才能花费那么长时间，更紧密的界限是O(n+m)。）

---

顶部，章节：1，2，3，4，5，6，7，8，9，A