这是一个创建于 3055 天前的主题，其中的信息可能已经有所发展或是发生改变。
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
请指点。
第 1 条附言 · 2016-07-13 16:03:34 +08:00
已解决！
新建长度为 n 的数组，也是对数组元素访问了 n 次，少数了。
 |
1
yemenchun1 2016-07-13 16:34:33 +08:00
 )教授为啥算的~3n? 我算的为什么是 5n-2 = n(n 个新元素) + 2n-1(翻倍时复制旧数组) + 2n-1(翻倍时找新数组的位置)呀? 什么样算访问一次数组? |
Select Language