Python - 摊销分析

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

如果列表已经排序，那么数据的分布情况并不重要。但是，列表的长度当然会产生影响，因为它决定了算法为获得最终结果而必须执行的步骤数。

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

• 会计方法- 这涉及为执行的每个操作分配成本。如果实际操作完成得比指定时间快，那么在分析中就会积累一些积极的信用。

在相反的情况下，它将是负信用。为了跟踪这些累积的积分，我们使用堆栈或树数据结构。较早执行的操作（如对列表进行排序）具有较高的摊余成本，但随着累积信用的使用，较晚执行的操作具有较低的摊余成本。因此，摊余成本是实际成本的上限。

• 潜在方法- 在这种方法中，保存的信用作为数据结构状态的数学函数用于未来的操作。数学函数的评估和摊余成本应该是相等的。因此，当实际成本大于摊余成本时，潜力就会减少，并且将其用于昂贵的未来运营。

• 聚合分析- 在这种方法中，我们估计 n 个步骤的总成本的上限。摊余成本是总成本与步骤数 (n) 的简单除法。