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
请指点。
)