设计和分析方法

为了测量算法的资源消耗，使用了本章讨论的不同策略。

渐近分析

函数f(n)的渐近Behave是指f(n)随着n变大而增长。

我们通常会忽略n的小值，因为我们通常有兴趣估计程序在大输入上的速度有多慢。

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

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

求解递归方程

递推是一个方程或不等式，它根据较小输入的值来描述函数。递归通常用于分治范式。

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

如果问题规模足够小，例如n < c，其中c是常数，则直接解决方案需要常数时间，记为θ(1)。如果问题的划分产生了许多大小为$\frac{n}{b}$的子问题。

解决该问题所需的时间为aT(n/b)。如果我们考虑除法所需的时间为D(n)，合并子问题结果所需的时间为C(n)，则递推关系可以表示为 -

$$T(n)=\begin{案例}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \:\:\:\:\theta(1) & 如果\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & 否则\end{案例}$$

可以使用以下方法解决递归关系 -

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

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

  • Master's Theorem - 这是查找递归关系复杂性的另一项重要技术。

摊销分析

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

  • 摊销分析提供了整个序列的实际成本的界限，而不是单独限制操作序列的成本。

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

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

聚合法

聚合方法给出了问题的全局视图。在该方法中，如果n次操作总共花费最坏情况时间T(n) 。那么每次操作的摊余成本就是T(n)/n。尽管不同的操作可能需要不同的时间，但在该方法中忽略了不同的成本。

核算方法

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

如果第 i次操作的实际成本和摊余成本分别为 $c_{i}$ 和 $\hat{c_{l}}$，则

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

电位法

该方法将预付费工作视为势能，而不是将预付费工作视为信用。这些能量可以被释放来支付未来的运营费用。

如果我们从初始数据结构D 0开始执行n次操作。让我们考虑，c i为实际成本，D i为第 i次操作的数据结构。势函数 Ф 映射到实数 Ф( Di ) ，即Di的相关势。摊余成本 $\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})$ $

动态表

如果为表分配的空间不够，我们必须将表复制到更大尺寸的表中。同样，如果从表中删除大量成员，最好重新分配较小大小的表。

使用摊余分析，我们可以证明插入和删除的摊余成本是恒定的，动态表中的未使用空间永远不会超过总空间的恒定比例。

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