简述
摊销分析涉及估计程序中操作序列的运行时间，而不考虑输入值中数据分布的跨度。一个简单的例子是在排序列表中查找值比在未排序列表中更快。
如果列表已经排序，则数据的分布程度无关紧要。但是，列表的长度当然会产生影响，因为它决定了算法必须经过多少步才能获得最终结果。
所以我们看到，如果获取排序列表的单个步骤的初始成本很高，那么后续步骤查找元素的成本就会变得相当低。因此，摊销分析可以帮助我们找到一系列操作的最坏情况运行时间的界限。摊销分析有三种方法。
-
Accounting Method− 这涉及为执行的每个操作分配成本。如果实际操作完成的速度比指定的时间快，那么分析中就会积累一些积极的信用。
在相反的情况下，它将是负信用。为了跟踪这些累积的学分，我们使用堆栈或树数据结构。较早执行的操作（如对列表进行排序）具有较高的摊销成本，但随着累积信用的使用，顺序较晚的操作具有较低的摊销成本。所以摊销成本是实际成本的上限。
-
Potential Method− 在这种方法中，保存的信用用于未来的操作，作为数据结构状态的数学函数。数学函数的评估和摊销成本应该相等。因此，当实际成本大于摊销成本时，潜力就会下降，并将其用于未来昂贵的运营。
-
Aggregate analysis − 在这种方法中，我们估计了 n 步总成本的上限。摊销成本是总成本和步数 (n) 的简单除法。
