返回信息流*Algorithms (4th edition)*第199页均摊分析那里，对于一个通过[resizing array实现的栈](https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/ResizingArrayStack.java.html)，假设N是2的幂，从空栈开始，连续N次push操作需要访问多少次数组。书上是N + 4 + 8 + 16 + ... + 2N = 5N - 4，第一个N是每个push都需要固定访问一次数组，但是后面的4 + 8 + 16 + ... + 2N我不知道是怎么来的。我的想法是：数组初始化长度为2，前两次push不会resize，第三次push操作会把数组长度从2翻倍到4，同时访问两次数组以把原来栈中的元素复制到新数组，第五次push操作会把数组长度从4翻倍到8，同时访问4次数组以把原来栈中的元素复制到新数组... 后面那部分就应该是 2 + 4 + N/2 啊。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96116同步于 2018/6/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【已解决】【问题】算法第四版的均摊分析
youdianer
2018/6/17镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
后面Q&A部分说，int[] a = new int[N]也表示访问N次数组，然后综合像你说的原数组访问一下算一次，复制目标数组的时候算一次，这样的话第二次push创建长度为2的数组+2就是4次，第三次push创建长度为4的数组+4就是8次，第(N/2+1)次push就是2N次，就正确了。
顺便后面那个proposition E的证明也清楚了。
谢谢。[ema25]
【 在 w350053002 的大作中提到: 】
: 会不会是原数组访问一下算一次，复制的目标数组访问一下算一次。。
好像还有点问题。。。
```
if (n == a.length) resize(2*a.length); // double size of array if necessary
a[n++] = item;
```
代码里当n为2的倍数时才会有复制的行为，也就是第3次，第5次push的时候会有复制。而主贴给出来的公式里面相当于第2次和第4次就复制了。。。
【 在 youdianer 的大作中提到: 】
: 后面Q&A部分说，int[] a = new int[N]也表示访问N次数组，然后综合像你说的原数组访问一下算一次，复制目标数组的时候算一次，这样的话第二次push创建长度为2的数组+2就是4次，第三次push创建长度为4的数组+4就是8次，第(N/2+1)次push就是2N次，就正确了。
: 顺便后面那个proposition E的证明也清楚了。
: 谢谢。
给的那个链接和书上的原代码有点小区别。
```python
#这是书上的代码
private Item[] a = (Item[]) new Object[1];
```
书上的源代码初始化的时候数组的长度为1，所以会在第二次push的时候产生复制（将长度为1的数组扩大到2，创建长度为2的数组访问数组2次，将原来数组的一个元素复制到新数组需访问数组2次，加起来就是4次），然后会在第三次push的时候产生复制（将长度为2的数组扩大到4，创建长度为4的数组访问数组4次，将原来数组的两个元素复制到新数组需访问数组4次，加起来就是8次），一直到第（N/2+1）次push操作访问数组(2N)次，就是4 + 8 + 16 + ... + 2N
【 在 w350053002 的大作中提到: 】
: 好像还有点问题。。。
: [md]
: ```
: ...................