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