Python Data Structure 简明教程

Python - Amortized Analysis

摊销分析涉及估算程序中一系列操作的运行时间，而不考虑输入值中数据分布的跨度。一个简单的例子是在排序列表中查找值比在未排序列表中查找值更快。

如果列表已经排序，那么数据如何分布并不重要。但当然列表的长度会产生影响，因为它决定了算法必须经历的步骤数才能得到最终结果。

因此，我们看到，如果获取排序列表的单个步骤的初始成本很高，则查找元素的后续步骤的成本会大大降低。因此，摊销分析可帮助我们找到一系列操作的最坏情况运行时间的界限。摊销分析有三种方法。

  1. Accounting Method − 这涉及为执行的每个操作分配一个成本。如果实际操作完成得比分配的时间快，那么一些正面积分就会在分析中累积起来。

  2. Potential Method − 在这种方法中，保存的积分被用于未来的操作，作为数据结构状态的数学函数。数学函数的评估和摊销成本应该相等。所以当实际成本大于摊销成本时，潜力会下降，并且被用于未来昂贵的操作。

  3. *总体分析 *− 在这种方法中，我们估算 n 步总成本的上限。摊销成本是总成本和步数 (n) 的简单除法。