平摊分析
维基百科,自由的 encyclopedia
平摊分析(英语:Amortized analysis)在电脑科学中,是用于算法分析中的方法,平摊分析常用于分析数据结构(动态的数据结构),在使用平摊分析前须知道数据结构各种操作所可能发生的时间,并计算出最坏情况下的操作情况并加以平均,得到操作的平均耗费时间。平摊分析只能确保最坏情况性能的每次操作耗费的平均时间,并不能确认平均情况性能。
一个简单的例子,一个长度为 的list,在list的最后要加入一笔新的资料此时要花费的操作时间为 ,此时也是加入新的资料的最糟糕的情况。但是,一个 个插入的操作序列仍然可以在 的时间内完成,因为剩下的插入可以在常数时间内完成,因此 个插入可以在 的时间内完成。因此每操作的平摊耗费为 。
注意平摊分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中,我们平均化所有可能的输入;在概率算法的概率分析中,我们平均化所有可能的随机选择;在平摊分析中,我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。[1]
平摊分析中几种常用的技术: