Python - 摊销分析

分期分析包括估算程序中操作序列的运行时间，而不考虑输入值中数据分布的范围。一个简单的例子是在排序列表中查找值比在未排序列表中快。如果列表已经排序，则数据分布的方式无关紧要。但是，当然，列表的长度会影响算法，因为它决定算法必须经过的步骤才能获得最终结果。

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

• 会计方法 - 这涉及为每个执行的操作分配成本。 如果实际操作比指定的时间更快结束，那么分析中会积累一些积极的信用。在相反的情况下，它将是负信贷。为了跟踪这些累计学分，我们使用堆栈或树形数据结构。早期进行的操作（如清单分类）具有较高的摊销成本，但随着积累的信用被利用，较晚的操作具有较低的摊销成本。所以摊余成本是实际成本的上限。

• 潜在方法 - 在这种方法中，将保​​存的信用作为数据结构状态的数学函数用于将来的操作。 数学函数的评估和摊销成本应该是相等的。因此，当实际成本高于摊销成本时，潜在价值会下降，并且将用于未来昂贵的运营。

• 综合分析 - 在这种方法中，我们估计n步骤总成本的上限。 摊销成本是总成本和步骤数（n）的简单划分。