算法的摊销分析

Question

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

Answer 1

摊销分析给出了最坏情况下每项操作的平均性能(随时间变化).

在一系列操作中,最坏的情况并不经常发生在每个操作中 - 一些操作可能很便宜,一些操作可能很昂贵.因此,传统的最坏情况下每个操作分析可能会给出过度悲观的限制.例如,在动态数组中,只有一些插入需要一个线性时间,而其他插入则需要一个恒定的时间.

当不同的插入时间不同时,我们如何准确计算总时间？摊销方法将为序列中的每个操作分配"人工成本",称为操作的摊余成本.它要求序列的总实际成本应受所有业务的摊余成本总额的限制.

请注意,摊销成本的分配有时会有灵活性.在摊销分析中使用三种方法

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

例如,假设我们正在对一个数组进行排序,其中所有的键都是不同的(因为这是最慢的情况,如果我们没有对等于它的键执行任何特殊操作,则会花费相同的时间.枢).

Quicksort选择一个随机的枢轴.枢轴同样可能是最小的键,第二小的,第三小的,......,或最大的.对于每个密钥,概率为1/n.设T(n)是一个随机变量,等于快速排序在n个不同键上的运行时间.假设quicksort选择第i个最小的键作为枢轴.然后我们在长度为i-1的列表上以及在长度为n-i的列表上递归地运行quicksort.分区和连接列表花费O(n)时间 - 最多n美元 - 所以运行时间是

这里我是一个随机变量,可以是从1(枢轴是最小的密钥)到n(枢轴是最大的密钥)的任意数字,每个都以1/n的概率选择,所以

该等式称为重复.重复的基本情况是T(0)= 1和T(1)= 1.这意味着对长度为零或一的列表进行排序最多需要1美元(单位时间).

所以当你解决时:

表达式1 + 8j log_2 j可能过高估计,但无关紧要.重要的是,这证明E [T(n)]在O(n log n)中.换句话说,快速排序的预期运行时间是O(n log n).

在摊销的运行时间和预期的运行时间之间也有一个微妙但重要的差异.具有随机枢轴的Quicksort需要O(n log n)预期运行时间,但其最坏情况运行时间为Θ(n ^ 2).这意味着快速排序很可能花费(n ^ 2)美元,但随着n变大,这种情况发生的可能性接近零.

Quicksort O(n log n)预期时间
QuickselectΘ(n)预期时间

对于数字示例:

基于比较的排序下限是:

最后,您可以在此处找到有关quicksort平均案例分析的更多信息

Answer 2

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

摊销 - 非概率分析,根据一批对算法的调用计算得出.

示例 - 动态大小的堆栈:

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

总的来说我们的成本是

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

• 堆栈已满时每次插入(分配和复制)O(n)

所以现在我们问,插入需要多长时间？

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

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

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

现在,只有当堆栈具有以下数量的元素时,我们才会执行完整复制:

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

对于这些尺寸中的每一个,我们都进行复制和分配,以便总结我们获得的成本:

const*(1 + 2 + 4 + 8 + ... + n/4 + n/2 + n)= const*(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

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

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