algorithm - 动态堆栈的摊销分析

Question

以下是有关动态堆栈的分摊分析的文本片段。

If we are implementing stack as a dynamic array. Say that inserting into the array costs 1, taking an element out of array costs 1, and the cost of resizing the array is the number of elements moved. (Say that all other operations, like incrementing or decrementing "top" are free). If we decide to double the size of the array when we resize. Now, in any sequence of "n" operations, the total cost for resizing is 1 +2 + 4+8 +...+(2^i) (i.e, 2 to power of i) for some 2^i < n ( if all operations are pushes then (2 ^i) will be largest power of 2 less than n). The sum is atmost 2n - 1. Adding in the additional cost of "n" for inserting/removing, we get a total cost < 3n, and our amoritzed cost per operations is < 3.

我的问题是作者如何得出总和最多为 2n -1 的结论。请求提供示例或证明方面的帮助。

谢谢!

Answer 1

它是一个geometric progression的总和:

SUM(q^k for k = 0 to n) = (q ^n+1 -1)/ (q-1)

那么在你的情况下你有:

SUM(2^k for k = 0 to i) = 2^(i+1) - 1 

那么从 2^i < n

2^(i+1) < 2n 

和

SUM(2^k for k = 0 to i) = 2^(i+1) - 1 < 2n - 1