分析方法

---

---

为了衡量算法的资源消耗，使用了不同的策略，如本章所述。

渐近分析

函数f(n)的渐近行为是指n变大时f(n)的增长情况。

我们通常忽略n的小值，因为我们通常感兴趣的是估计程序在大型输入上的运行速度。

一个好的经验法则是，渐近增长率越慢，算法越好。尽管这并不总是正确的。

例如，线性算法$f(n) = d * n + k$在渐近意义上总是优于二次算法$f(n) = c.n^2 + q。

求解递推方程

递推关系是一个用较小输入上的函数值来描述函数的方程或不等式。递推关系通常用于分治范式。

让我们考虑T(n)为大小为n的问题的运行时间。

如果问题规模足够小，例如n < c，其中c是一个常数，则直接解法需要常数时间，写成θ(1)。如果问题的划分产生了一些大小为$\frac{n}{b}$的子问题。

为了解决这个问题，所需时间为a.T(n/b)。如果我们考虑划分所需的时间为D(n)，组合子问题结果所需的时间为C(n)，则递推关系可以表示为 -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

可以使用以下方法求解递推关系 -

• 代入法 - 在这种方法中，我们猜测一个界限，并使用数学归纳法证明我们的假设是正确的。

• 递归树法 - 在这种方法中，形成一个递归树，其中每个节点代表成本。

• 主定理 - 这是另一种找到递推关系复杂度的重要技术。

摊还分析

摊还分析通常用于执行一系列类似操作的某些算法。

• 摊还分析提供整个序列的实际成本的上界，而不是分别对操作序列的成本进行边界限制。

• 摊还分析不同于平均情况分析；概率不涉及摊还分析。摊还分析保证了最坏情况下每个操作的平均性能。

它不仅仅是一个分析工具，它是一种思考设计的思路，因为设计和分析是密切相关的。

聚合方法

聚合方法提供了问题的全局视图。在这种方法中，如果n个操作总共需要最坏情况时间T(n)。那么每个操作的摊还成本为T(n)/n。虽然不同的操作可能需要不同的时间，但在这种方法中忽略了变化的成本。

记账方法

在这种方法中，根据操作的实际成本为不同的操作分配不同的费用。如果操作的摊还成本超过其实际成本，则将差额作为信用分配给对象。此信用有助于支付摊还成本低于实际成本的后续操作。

如果第i^th个操作的实际成本和摊还成本为$c_{i}$和$\hat{c_{l}}$，则

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

势能方法

此方法将预付工作表示为势能，而不是将预付工作视为信用。这种能量可以释放出来支付未来的操作。

如果我们执行n个操作，从初始数据结构D₀开始。让我们考虑c_i为实际成本，D_i为第i^th个操作的数据结构。势函数Ф映射到一个实数Ф(D_i)，即D_i的相关势能。摊还成本$\hat{c_{l}}$可以定义为

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

因此，总的摊还成本为

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

动态表

如果为表分配的空间不足，则必须将表复制到更大的表中。类似地，如果从表中删除了大量成员，则最好将表重新分配为更小的尺寸。

使用摊还分析，我们可以证明插入和删除的摊还成本是常数，并且动态表中未使用的空间永远不会超过总空间的常数部分。

在本教程的下一章中，我们将简要讨论渐近符号。