ven*_*rty 40 algorithm analysis
我正在阅读一篇关于算法的摊销分析的文章.以下是文本摘要.
摊销分析与平均案例分析类似,因为它涉及一系列操作的平均成本.但是,平均案例分析依赖于有关数据结构和操作的概率假设,以便计算算法的预期运行时间.因此,它的适用性取决于关于算法输入的概率分布的某些假设.
平均情况限制并不排除即使输入概率分布的假设有效,人们也会"不幸"并遇到需要超过预期时间的输入的可能性.
我对上述文字片段的疑问是:
在第一段中,平均案例分析如何"依赖于关于数据结构和操作的概率假设？"我知道平均案例分析取决于输入概率,但上述陈述意味着什么？
作者在第二段中的意思是,即使输入分布有效,平均情况也无效？
谢谢!
Ros*_*ant 42
平均案例分析对在某些情况下可能无法满足的输入做出假设.因此,如果您的输入不是随机的,则在最坏的情况下,算法的实际性能可能比平均情况慢得多.
摊销分析没有做出这样的假设,但它考虑了一系列操作的总体性能而不仅仅是一个操作.
动态数组插入提供了一个简单的摊销分析示例.一种算法是分配固定大小的数组,并且在插入新元素时,在必要时分配固定大小的数组,该数组是旧长度的两倍.在最坏的情况下,插入可能需要与整个列表的长度成比例的时间,因此在最坏的情况下插入是O(n)操作.但是,您可以保证这种最坏情况很少发生,因此插入是使用摊销分析的O(1)操作.无论输入是什么,摊销分析都会保留.
Pat*_*k87 11
要获得平均时间复杂度,您需要假设"平均情况"是什么.如果输入是字符串,那么"平均字符串"是什么？只有长度重要吗？如果是这样,我将获得的字符串的平均长度是多少？如果不是,这些字符串中的平均字符是什么？如果字符串是例如姓氏,则很难肯定地回答这些问题.平均姓氏是多少？
在大多数有趣的统计样本中,最大值大于平均值.这意味着您的平均案例分析有时会低估某些输入所需的时间/资源(这是有问题的).如果你考虑一下,对于对称的PDF,平均案例分析应该低估它高估的程度.最糟糕的案例分析,OTOH,只考虑最有问题的案例,因此保证高估.
考虑未排序数组中最小值的计算。也许您知道它有 O(n)运行时间，但如果我们想要更精确，它会n/2在平均情况下进行比较。为什么这个？因为我们正在对数据做假设；我们假设最小值可以以相同的概率出现在每个位置。如果我们改变这个假设，并且我们说处于第 i 个位置的概率随着 i 的增加而增加，我们可以证明不同的比较数，甚至是不同的渐近界限。
在第二段中，作者说，通过平均案例分析，我们可能会非常不幸，测量到的平均案例大于理论案例；回想一下前面的例子，如果我们不幸在 m 个大小为 n 的不同数组上，并且最小值每次都在最后一个位置，那么我们将测量平均n情况而不是n/2。当摊销界限得到证明时，这不可能发生。