Python - 摊销分析

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

如果列表已排序，则数据的分布程度无关紧要。但当然，列表的长度也有影响，因为它决定了算法必须经过多少步才能获得最终结果。

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

• 会计方法 − 这涉及为执行的每项操作分配成本。如果实际操作的完成速度比分配的时间快，则分析中会累积一些正积分。
• 潜在方法 − 在此方法中，保存的信用作为数据结构状态的数学函数用于未来的操作。数学函数的计算结果和摊销成本应该相等。因此，当实际成本大于摊销成本时，潜力会降低，并将其用于昂贵的未来运营。
• 聚合分析 − 在此方法中，我们估计 n 个步骤的总成本的上限。摊销成本是总成本和步骤数 （n） 的简单除法..