算法的摊销分析

Question

我正在阅读摊销分析。我无法完全理解它与我们执行的计算算法的平均或最差情况行为的正常分析有何不同。有人可以用排序或其他的例子来解释吗？

Answer 1

摊销分析给出了 中最差情况下每项操作的平均表现（随时间变化）。

在一系列操作中，最糟糕的情况在每次操作中都不会经常发生 - 有些操作可能很便宜，有些操作可能很昂贵。因此，传统的最坏情况每次操作分析可能会给出过分悲观的界限。例如，在动态数组中，只有一些插入需要线性时间，但其他插入需要一定的时间。

当不同的插页需要不同的时间时，我们如何准确地计算总时间？摊销方法将为序列中的每个操作分配一个“人工成本”，称为操作的摊销成本。它要求序列的总实际成本应该以所有操作的摊销成本总额为界。

请注意，在分摊摊销成本时有时会有灵活性。 三种方法在平摊分析

1. 聚合方法（或蛮力）使用
2. 会计处理方法（或庄家的方法）
3. 电位法（或物理学家的方法）

对于实例假设我们正在对一个数组进行排序，在这个数组中，所有的键都是不同的（因为这是最慢的情况，并且它们需要的时间与它们不是时间的时间相同，如果我们没有对等于主键的键做任何特殊处理）。

快速排序选择随机数据透视。这个关键点同样可能是最小的关键点，第二小的关键点，第三小的关键点......或最大的关键点。对于每个键， 的概率是1/n。假设T（n）是一个随机变量，它等于在不同密钥上的快速排序的运行时间。假设快速排序选择第i个最小的键作为关键点。然后我们在长度为i - 1的列表上递归地运行quicksort，并在长度为n - i的列表上长度为 。这需要O（n）的时间来划分并连接所有的名单，让我们 说至多n美元，使运行的时间是

在这里，我是一个随机变量，它可以是任何数量从1（枢轴是 最小键）至n（枢轴是最大键），每个的概率是1/n的选择，所以

该方程被称为复发。重复的基本情况是T（0）= 1和T（1）= 1。这意味着排序长度为零或1的列表最多花费1美元（时间单位）。

所以，当你解决：

表达式1 + 8J log_2Ĵ可能被高估，但它不是做 问题。重要的是，这证明E [T（n）]在O（n log n）中。 换句话说，快速排序的预期运行时间是O（n log n）。

此外，摊销运行时间 与预计运行时间之间存在细微但重要的差异。具有随机枢轴的快速排序需要O（n log n）预期运行时间，但其最坏情况运行时间在Θ（n^2）中。这意味着存在一个很小的可能性，即快速排序会花费（n^2）美元，但是随着n增长，发生这种情况的可能性接近于零。

快速排序为O（n log n）的预期时间
QuickselectΘ（n）的预计时间

对于数字示例：

的基于比较的排序下界是：

最后，你可以找到更多信息有关快速排序的平均案例分析here

Answer 2

平均 - 概率分析，平均是相对于所有可能的输入，它的估计算法的可能运行时间。

摊销 - 非概率分析，与一批调用算法相关计算。

例子 - 活力大小的堆栈：

说，我们定义了一些大小的堆栈，每当我们使用最多的空间，我们分配两次老大小和元素复制到新的位置。

整体我们的成本是：

• O（1）每次插入\缺失

• ø每次插入（分配和复制）（n）的即使堆栈满

所以现在我们问，插入需要多少时间？

可能会说O（n^2），但是我们不会为每个插入付O（n）。 所以我们是悲观的，正确的答案是O（n）的时间对于n插入，让我们看看为什么：

可以说，我们先从数组的大小= 1

忽略复制我们将支付为O（n ）每插入一次。

现在，我们能做的只有当栈有这些数量的元素的完整副本：

1,2,4,8，...，N/2，N

对于这些（1 + 2 + 4 + 8 + ... + n/4 + n/2 + n）= const *（n（n） + 1/2 + 1/4 + 1/8 + ...）

其中， （1 + 1/2 + 1/4 + 1/8 + ...）= 2

所以我们支付O（n）的所有复制+ O（n）的实际n插入

O（n）n操作的最坏情况 - > O（1）每次操作摊销。