摊销成本、平均成本和预期成本之间的差额

Question

我在学习算法。摊销成本、平均成本和预期成本之间有什么不同？

Answer 1

算法的平均成本实际上是基于该算法可能处理的每一种情况的平均成本，并将其除以所述案例的数量。如果该算法可以分别在4个不同的输入A, B, C, D上工作在x, 2x, 3x, and 4x时间内，则其平均代价为；

(x + 2x + 3x + 4x) / 4 = 2.5 * x.

预期成本与平均成本相似，但也考虑到了输入发生的可能性。在相同的例子基础上，如果在输入A, B, C and D上工作的算法各自的概率分别为0.5, 0.3, 0.1, 0.1，则所期望的代价是；

(0.5 * x + 0.3 * 2x + 0.1 * 3x + 0.1 * 4x) = 1.8 * x.

摊销成本与上述两个概念略有不同。通常，在计算平均、最坏情况和预期时间代价时，我们将每个运算看作一个单一的等价步骤，并根据这些步骤的总数计算出算法的复杂性。然而，通过摊销分析，并没有假设每个操作是等价的。一个很好的例子是在大多数编程语言中实现动态调整大小的数组。

以STL的C++和std::vector为例。它以0的容量和大小开始。当您试图将一个元素推到它上时，它会分配一个1数组，并且容量和大小变成1。当您再次这样做时，容量和大小就变成了2。然而，下一次，即使1的大小增加了，容量也变成了4。当您填充4的容量时，在调整大小后，容量变为8，当填充该容量时，数组将调整为16大小。

此模式表明，并非对std::vector的每个插入都需要相同的执行时间，这是因为在某些插入过程中发生了调整大小的操作。然而，随着容量的增加，由于容量的翻倍，容量的增加就变得很大了。因此，插入期间调整大小的概率降低到这样一个水平，总的来说，我们实际上可以考虑插入的时间复杂性为常数。这是由于摊销分析。

与其同时考虑每一次操作，不如通过摊销分析，考虑昂贵操作的频率和成本及其与所执行操作总数的比例，并找出某些算法以更好(即更现实)的方式使用的实际时间。

例如，在std::vector实现中，如果将n插入到一个空向量，则只会出现logn昂贵的插入。(即需要调整大小和增加容量)，当考虑到这类业务的比率时，插入费用就会有固定的摊销成本。