摊销分析？(最坏情况下的履约保证)

Question

什么是摊销分析？它如何帮助我在我的程序中实现最坏的性能保证？

我是阅读，认为以下技术可以帮助程序员实现最坏的性能保证(用我自己的话说:保证程序的运行时间不会超过最坏的情况下的运行时间)：

• 随机算法(例如，在最坏情况下，快速排序算法是二次型的，但随机排序输入可以保证其运行时间是线性的)。
• 操作序列(我们的分析必须同时考虑到数据和客户端执行的操作顺序)
• 摊销分析(提供绩效保证的另一种方法是通过跟踪所有业务的总成本，除以业务数量，摊销成本。在这种情况下，我们可以允许一些昂贵的操作，同时保持操作的平均成本低。换句话说，我们通过将几个昂贵的操作分配给大量的廉价操作中的每一个来分摊成本)

作者将调整数组数据结构作为如何实现摊销分析的一个例子，但我仍然不明白什么是摊销分析，以及如何实现它(数据结构？算法？)以达到最差的性能保证

Answer 1

你不执行摊销分析。这是一种获得更精确的O边界的技术。

你必须要做的基本观察是，昂贵的手术不可能在任何时候发生。

在数组支持的数据结构中，数组需要不时调整大小--当它已满时。这是最昂贵的操作，需要O(n)时间。数组中的所有其他插入都是O(1)。

要确定插入n项的运行时，可以将n与最昂贵的操作O(n)相乘，这将导致O(n^2)的总体运行时行为。

然而，这是不准确的，因为调整大小不可能经常发生。

当你谈到钱，你摊销成本，当你偿还你的债务与多次小付款随着时间的推移。

我们也可以用这个模型来考虑算法。我们只需将“时间”替换为“金钱”，以避免心理映射。

一旦数组达到它的长度n，我们就可以使它的大小翻倍。我们需要进行以下操作：

• 分配2n内存块
• 复制n项目

如果我们假设分配内存和复制都发生在线性时间，这将是一个非常昂贵的操作。然而，我们现在可以利用债务的概念并将其摊销用于我们的分析。只是，我们要先摊还我们的债务，然后才能还清。

让我们假设，一旦我们调整了数组的大小，我们的余额(货币/时间)就会回到0(即我们没有债务，也没有任何剩饭)。

这意味着：

• 插入下一个n项将支付调整大小和复制的费用(我们有n使用的插槽，以及n未使用的时隙)

现在，我们可以考虑每个insert操作需要支付多少费用：

• 插入
• 分配一块内存的成本
• 将其移动到新分配的内存的成本。

我们现在已经支付了分配内存、复制和插入下一个n元素的费用。然而，我们还忽略了为旧的n元素分配空间以及复制它们。

我们只需将旧n元素的成本分配给新的(尚未插入) n元素：

• 分配一块内存的成本
• 将其移动到新分配的内存的成本。

总共，每一次插入操作将花费5个单元。这为它自己的插入，以及移动和分配空间为自己和旧元素之一付出了代价。

每个insert-操作仍然需要固定的时间，但是调整大小是免费的:我们通过在每个插入上花费“更多”时间来摊销它。

因此，插入n元素需要O(n)时间。

摊销分析的其他技术是在此解释。

Answer 2

首先，它是一种分析程序运行时的技术，而不是算法的实现技术。

列表中提到的示例是一个很好的例子:将单个项附加到数组支持的数据结构中。对于每一个附加操作，最坏的情况是必须复制所有现有的项目。这种分析太悲观了，因为如果您使用的是合理的调整大小策略(将大小乘以x> 1.0)，则不必这样做。然后分析说，您有一个O(n^2)绑定--每项O(n)乘以n项--而实际运行时仅为O(n)。

如果对插入的所有项目(其中大多数不需要调整大小)进行调整成本的平均值，则需要进行摊销分析。摊销分析的结果是一个O(n)界，与算法的实际行为相吻合。