关于《算法》（第 4 版）中对算法性能的均摊分析的疑问

[lxmfly123]

1.4.8.5 中所述：（对于算法 1.1 ，即动态调整数组大小的下压栈）假设 N 是 2 的幂。如果数据结构初始为空， N 次连续的 push() 调用需要访问数组元素 N + 4 +8 + 16 + ... + 2N = 5N - 4 次。而程序计数的结果却如下：

N: 1 counter: 1

N: 2 counter: 2

N: 4 counter: 10

N: 8 counter: 26

N: 16 counter: 58

N: 32 counter: 122

N: 64 counter: 250

N: 128 counter: 506

N: 256 counter: 1018

算法 1.1 链接 http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/ResizingArrayStack.java.html

请指点。

[yemenchun1]


教授为啥算的~3n?

我算的为什么是 5n-2 = n(n 个新元素) + 2n-1(翻倍时复制旧数组) + 2n-1(翻倍时找新数组的位置)呀?

什么样算访问一次数组?