将堆栈实现为数组的成本分析？
Cost analysis for implementing a stack as an array?
请参考上面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.
有人可以解释一下吗？
n是最大的堆栈大小，此时的内在数组大小是2的最小幂2^(i+1)>=n，所以最后一次扩容操作需要2^i<n时间。
例如，如果数组达到大小 n=11，最后一次扩展会导致从 8 增加到 16 并移动 8 个项目
关于第二题：几何级数和
1 + 2 + 4 + 8 + ... + 2^i = 2^(i+1) - 1
请参考上面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.
有人可以解释一下吗？
n是最大的堆栈大小，此时的内在数组大小是2的最小幂2^(i+1)>=n，所以最后一次扩容操作需要2^i<n时间。
例如，如果数组达到大小 n=11，最后一次扩展会导致从 8 增加到 16 并移动 8 个项目
关于第二题：几何级数和
1 + 2 + 4 + 8 + ... + 2^i = 2^(i+1) - 1