算法平摊分析 [英] Amortized Analysis of Algorithms

问题描述

我目前正在读平摊分析。我不能完全理解它是如何不同于正常分析，我们进行计算的算法平均或最坏情况下的行为。有人能整理或东西的例子解释一下吗？

I am currently reading amortized analysis. I am not able to fully understand how it is different from normal analysis we perform to calculate average or worst case behaviour of algorithms. Can someone explain it with an example of sorting or something ?

推荐答案

平摊分析给出了每个操作的平均业绩（一段时间内） 最坏的情况下

Amortized analysis gives the average performance (over time) of each operation in the worst case.

在操作序列最坏的情况下并不常发生在每一个操作 - 一些操作可以是便宜的，一些可能是昂贵的。因此，每个操作分析一个传统的最坏情况下，可以给过于悲观界。例如，在动态阵列只有一些插入取一个线性时间，尽管其他人 - 恒定时间

In a sequence of operations the worst case does not occur often in each operation - some operations may be cheap, some may be expensive Therefore, a traditional worst-case per operation analysis can give overly pessimistic bound. For example, in a dynamic array only some inserts take a linear time, though others - a constant time.

当插入不同采取不同的时代，怎样才能准确地计算出总的时间？该摊销的方法是要在序列中指定一个人工费为每一个操作，称为操作的摊余成本。它要求该序列的总真实成本应该由所有操作的摊销成本的合计为界。

When different inserts take different times, how can we accurately calculate the total time? The amortized approach is going to assign an "artificial cost" to each operation in the sequence, called the amortized cost of an operation. It requires that the total real cost of the sequence should be bounded by the total of the amortized costs of all the operations.

请注意，有有时摊销费用的分配的灵活性。 三种方法在平摊分析中使用

Note, there is sometimes flexibility in the assignment of amortized costs. Three methods are used in amortized analysis

1. 在聚合方法（或蛮力）
2. 在核算方法（或银行家的方法）
3. 电位法（或物理学家的方法）

例如假设我们正在整理一个数组中所有的键是不同的（因为这是最慢的情况，并采取相同的时间量的时候都没有，如果我们没有做什么特别的钥匙这等于支点）。

For instance assume we’re sorting an array in which all the keys are distinct (since this is the slowest case, and takes the same amount of time as when they are not, if we don’t do anything special with keys that equal the pivot).

快速排序随机选择一个支点。枢轴是同样可能是最小的键， 第二小的，第三最小，...，或最大的。对于每一个键， 概率为1 / N。设T（n）是一个随机变量等于快速排序的对运行的时间 n个不同的密钥。假设快速排序选取第i个最小键作为支点。然后我们长度的列表上运行快速排序递归I - 1和列表 长度为n - 我。它需要O（n）的时间来划分并连接所有的名单，让我们 说的最多n块钱，所以运行时间

Quicksort chooses a random pivot. The pivot is equally likely to be the smallest key, the second smallest, the third smallest, ..., or the largest. For each key, the probability is 1/n. Let T(n) be a random variable equal to the running time of quicksort on n distinct keys. Suppose quicksort picks the ith smallest key as the pivot. Then we run quicksort recursively on a list of length i − 1 and on a list of length n − i. It takes O(n) time to partition and concatenate the lists–let’s say at most n dollars–so the running time is

下面i是，可以是任何数目，从1的随机变量（枢轴是 最小的键）至n（枢轴是最大键），每个选择的概率是1 / n时， 所以

Here i is a random variable that can be any number from 1 (pivot is the smallest key) to n (pivot is largest key), each chosen with probability 1/n, so

这个公式被称为复发。基座例为复发为T（0）= 1和T（1）= 1，这意味着，排序长度为0或1的列表需要至多一个元（时间单位）。

This equation is called a recurrence. The base cases for the recurrence are T(0) = 1 and T(1) = 1. This means that sorting a list of length zero or one takes at most one dollar (unit of time).

所以，当你解决：

这位前pression 1 + 8J log_2Ĵ可能被高估，但它不 物。最重要的一点是，这证明了E [T（N）]是为O（n log n）的。 换句话说，快速排序的预计运行时间为O（N日志N）。

The expression 1 + 8j log_2 j might be an overestimate, but it doesn’t matter. The important point is that this proves that E[T(n)] is in O(n log n). In other words, the expected running time of quicksort is in O(n log n).

另外还有摊销的运行时间之间的微妙而重要的迪FF erence 和预期的运行时间。快速排序随机支点花费为O（n log n）的预计运行时间，但其运行时间最坏的情况是在Θ（N ^ 2）。这意味着，有一个小 可能性，快速排序将花费（N ^ 2）美元，但概率，这 会发生接近零随着n变大。

Also there’s a subtle but important difference between amortized running time and expected running time. Quicksort with random pivots takes O(n log n) expected running time, but its worst-case running time is in Θ(n^2). This means that there is a small possibility that quicksort will cost (n^2) dollars, but the probability that this will happen approaches zero as n grows large.

快速排序为O（n log n）的预期时间
  QuickselectΘ（n）的预计时间

Quicksort O(n log n) expected time
Quickselect Θ(n) expected time

有关数字为例：

比较基础的排序下限是：

The Comparison Based Sorting Lower Bound is:

最后，你可以在这里找到快速排序的平均案例分析更多信息

Finally you can find more information about quicksort average case analysis here

这篇关于算法平摊分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！