Python Data Structure 简明教程

Python - Amortized Analysis

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

Amortized analysis involves estimating the run time for the sequence of operations in a program without taking into consideration the span of the data distribution in the input values. A simple example is finding a value in a sorted list is quicker than in an unsorted list.

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

If the list is already sorted, it does not matter how distributed the data is. But of course the length of the list has an impact as it decides the number of steps the algorithm has to go through to get the final result.

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

So we see that if the initial cost of a single step of obtaining a sorted list is high, then the cost of subsequent steps of finding an element becomes considerably low. So Amortized analysis helps us find a bound on the worst-case running time for a sequence of operations. There are three approaches to amortized analysis.

  1. Accounting Method − This involves assigning a cost to each operation performed. If the actual operation finishes quicker than the assigned time then some positive credit is accumulated in the analysis.

  2. Potential Method − In this method the saved credit is utilized for future operations as mathematical function of the state of the data structure. The evaluation of the mathematical function and the amortized cost should be equal. So when the actual cost is greater than amortized cost there is a decrease in potential and it is used utilized for future operations which are expensive.

  3. *Aggregate analysis * − In this method we estimate the upper bound on the total cost of n steps. The amortized cost is a simple division of total cost and the number of steps (n)..