algorithm - 将堆栈实现为数组的成本分析？

Question

请引用上述 Material 的答案2。我可以跟随文本到那一点。当没有插图时，我似乎总是会松散概念化，这可能是因为我是数学符号的新手。

我了解昂贵操作的成本(当堆栈已满时将数组加倍)

1 + 2 + 4 + 8 + ... + 2^i 其中 i 是该序列的索引。所以索引 0 = 1、1 = 2、2 = 4 和 3 = 8。

我可以看到代价高昂的操作的顺序，但我对以下解释感到困惑。

Now, in any sequence of n operations, the total cost for resizing is 1 + 2 + 4 + 8 + ... + 2^i for some 2^i < n (if all operations are pushes then 2^i will be the largest power of 2 less than n). This sum is at most 2n − 1. Adding in the additional cost of n for inserting/removing, we get a total cost < 3n, and so our amortised cost per operation is < 3

我不明白那个解释？

the total cost for resizing is 1 + 2 + 4 + 8 + ... + 2^i for some 2^i < n

这对一些人来说意味着什么 2^i < n

是不是说操作次数n总是大于2^i？ n是操作次数还是数组长度？

以下我只是不遵循:

if all operations are pushes then 2^i will be the largest power of 2 less than n. This sum is at most 2n − 1.

有人可以解释一下吗？

Answer 1

n是最大的堆栈大小，此时固有数组大小是两个的最小幂 2^(i+1)>=n , 所以最后一个扩展操作需要 2^i<n时间。

例如，如果数组达到大小 n=11 ，最后一次扩展导致从 8 增加到 16，移动了 8 个项目

关于第二题:几何级数和

1 + 2 + 4 + 8 + ... + 2^i = 2^(i+1) - 1