algorithm - 算法的摊销分析

Question

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

Answer 1

摊销分析给出了最坏情况下每个操作的平均性能（随着时间的推移）。

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

当不同的插入所用的时间不同时，我们如何才能准确地计算出总时间呢？摊销方法将为序列中的每个操作分配一个“人为成本”，称为操作的摊销成本。它要求序列的总实际成本应受所有操作的摊销成本总和的限制。

请注意，摊销成本的分配有时具有灵活性。摊销分析中使用了三种方法

1. 聚合方法（或蛮力）
2. 会计方法（或银行家方法）
3. 势法（或物理学家的方法）

例如，假设我们正在对一个数组进行排序，其中所有键都是不同的（因为这是最慢的情况，并且如果我们不对等于枢）。

快速排序选择一个随机枢轴。枢轴同样可能是最小的键、第二小的键、第三小的键、...或最大的键。对于每个键，概率为 1/n。令 T(n) 是一个随机变量，等于对 n 个不同键进行快速排序的运行时间。假设快速排序选择第 i 个最小的键作为枢轴。然后我们在长度为 i-1 的列表和长度为 n-i 的列表上递归运行快速排序。划分和连接列表需要 O(n) 时间——假设最多 n 美元——所以运行时间是

这里 i 是一个随机变量，可以是从 1（pivot 是最小键）到 n（pivot 是最大键）的任何数字，每个选择的概率为 1/n，所以

这个方程称为递归。重复的基本情况是 T(0) = 1 和 T(1) = 1。这意味着对长度为 0 或 1 的列表进行排序最多需要 1 美元（时间单位）。

所以当你解决：

表达式 1 + 8j log_2 j 可能被高估了，但这并不重要。重要的一点是，这证明了 E[T(n)] 在 O(n log n) 中。换句话说，快速排序的预期运行时间是 O(n log n)。

此外，摊销运行时间和预期运行时间之间存在细微但重要的差异。具有随机枢轴的快速排序需要 O(n log n) 的预期运行时间，但其最坏情况的运行时间是 Θ(n^2)。这意味着快速排序花费 (n^2) 美元的可能性很小，但是随着 n 变大，这种情况发生的概率接近于零。

快速排序 O(n log n) 预期时间
快速选择 Θ(n) 预期时间

对于数字示例：

基于比较的排序下界是：

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

Answer 2

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

摊销- 非概率分析，根据对算法的一批调用计算。

示例 - 动态大小的堆栈：

假设我们定义了一个一定大小的堆栈，每当我们用完空间时，我们分配旧大小的两倍，并将元素复制到新位置。

总的来说，我们的成本是：

• O(1) 每次插入\删除

• 当堆栈已满时，每次插入（分配和复制）的 O(n)

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

有人可能会说 O(n^2)，但我们不会为每次插入支付 O(n)。所以我们很悲观，正确的答案是 n 次插入的 O(n) 时间，让我们看看为什么：

假设我们从数组大小 = 1 开始。

忽略复制，我们将为每 n 次插入支付 O(n)。

现在，我们仅在堆栈具有以下数量的元素时才进行完整复制：

1,2,4,8,...,n/2,n

对于这些大小中的每一个，我们都会进行复制和分配，所以总结一下我们得到的成本：

常量*(1+2+4+8+...+n/4+n/2+n) = 常量*(n+n/2+n/4+...+8+4+2+1 ) <= const*n(1+1/2+1/4+1/8+...)

其中 (1+1/2+1/4+1/8+...) = 2

所以我们为所有的复制支付 O(n) + 为实际的 n 次插入支付 O(n)

n 次操作的 O(n) 最坏情况 -> O(1) 每一次操作摊销。