Python - 均摊分析

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

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

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

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

势能方法 - 在这种方法中，保存的信用额度被用作数据结构状态的数学函数，用于未来的操作。数学函数的评估和均摊成本应该相等。因此，当实际成本大于均摊成本时，势能会下降，并将其用于未来的昂贵操作。
聚合分析 - 在这种方法中，我们估计 n 步总成本的上限。均摊成本是总成本与步数 (n) 的简单除法。。

打印页面