algorithm - 算法的摊销分析

Question

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

Answer 1

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

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

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

请注意，摊余成本的分配有时具有灵 active 。 摊销分析使用三种方法

1. 聚合方法(或蛮力法)
2. 会计方法(或银行家的方法)
3. 潜在方法(或物理学家的方法)

例如，假设我们正在对一个数组进行排序，其中所有的键都是不同的(因为这是最慢的情况，并且如果我们不对键做任何特殊的事情，那么所花的时间与它们不相同时所花的时间相同)等于枢轴)。

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

这里的 i 是一个随机变量，可以是从 1 开始的任意数字(轴心是 最小的键)到 n(枢轴是最大的键)，每个选择的概率为 1/n， 所以

这个等式称为递归。递归的基本情况是 T(0) = 1 和 T(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 变大，将接近于零。

Quicksort O(n log n) expected time
Quickselect Θ(n) expected time

举个数字例子:

基于比较的排序下界是:

终于可以找到更多关于quicksort average case analysis的信息here