我正在阅读一篇关于算法的摊销分析的文章.以下是文本摘要.
摊销分析与平均案例分析类似,因为它涉及一系列操作的平均成本.但是,平均案例分析依赖于有关数据结构和操作的概率假设,以便计算算法的预期运行时间.因此,它的适用性取决于关于算法输入的概率分布的某些假设.
平均情况限制并不排除即使输入概率分布的假设有效,人们也会"不幸"并遇到需要超过预期时间的输入的可能性.
我对上述文字片段的疑问是:
在第一段中,平均案例分析如何"依赖于关于数据结构和操作的概率假设？"我知道平均案例分析取决于输入概率,但上述陈述意味着什么？
作者在第二段中的意思是,即使输入分布有效,平均情况也无效？
谢谢!