Python数据结构 平摊分析

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

如果列表已经被排序了，那么数据的分布情况就不重要了。但当然，列表的长度也有影响，因为它决定了算法获得最终结果所需的步骤数量。

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

• 核算法– 这涉及到给每个执行的操作分配一个成本。如果实际操作完成的时间比分配的时间快，那么在分析中就会积累一些正数。

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

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

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