Python - 摊销分析

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

如果列表已经排序，则数据的分布情况无关紧要。 但是，列表的长度当然会产生影响，因为它决定了算法为获得最终结果而必须经过的步骤数。

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

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

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

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

• 聚集方法 − 在这种方法中，我们估计了 n 个步骤的总成本的上限。 摊销成本是总成本与步骤数 (n) 的简单除法。