算法 4 中的均摊分析

[Higurashi]

《算法（第四版）》 1.4.8.5 节“均摊分析”中有这样一个命题：

命题 E 。在基于可调整大小的数组实现的 Stack 数据结构中（请见算法 1.1 ），对空数据结构所进行的任意操作序列对数组的平均访问次数在最坏情况下均为常数。
Proposition E. In the resizing array implementation of Stack (Algorithm 1.1), the average number of array accesses for any sequence of operations starting from an empty data structure is constant in the worst case.

随后给出的简略证明为：

对于每次使数组大小增加（假设大小从 N 变为 2N ）的 push()操作，对于 N/2+2 到 N 之间的任意 k ，考虑使栈大小增长到 k 的最近 N/2-1 次 push()操作。将使数组长度加倍所需的 4N 次访问和所有 push()操作所需的 N/2 次数组访问（每次 push()操作均需访问一次数组）取平均，我们可以得到每次操作的平均成本为 9 次数组访问。
Proof sketch: For each push() that causes the array to grow (say from size N to size 2N), consider the N/2 1 push() operations that most recently caused the stack size to grow to k, for k from N/2 + 2 to N. Averaging the 4N array accesses to grow the array with N/2 array accesses (one for each push), we get an average cost of 9 array accesses per operation.

简单来说，我看不懂这个证明，能否帮忙解释一下？任何想法或提示都可能有帮助，谢谢。

算法 1.1：

import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item>
{
    private Item[] a = (Item[]) new Object[1];  // 栈元素
    private int N = 0;                             // 元素数量
    public boolean isEmpty()  {  return N == 0; }
    public int size()          {  return N;       }
    private void resize(int max)
    {  // 将栈移动到一个大小为 max 的新数组
      Item[] temp = (Item[]) new Object[max];
      for (int i = 0; i ＜ N; i++)
          temp[i] = a[i];
      a = temp;
    }
    public void push(Item item)
    {  // 将元素添加到栈顶
      if (N == a.length) resize(2 * a.length);
      a[N++] = item;
    }
    public Item pop()
    {  // 从栈顶删除元素
      Item item = a[--N];
      a[N] = null;  // 避免对象游离（请见 1.3.2.4 节）
      if (N ＞ 0 && N == a.length/4) resize(a.length/2);
      return item;
  }
  public Iterator ＜ Item ＞ iterator()
    {  return new ReverseArrayIterator();  }
  private class ReverseArrayIterator implements Iterator<Item>
  {  // 支持后进先出的迭代
      private int i = N;
      public boolean hasNext() {  return i ＞ 0;   }
      public    Item next()    {  return a[--i];  }
      public    void remove()  {                    }
  }
}

[lance6716]

之所以需要均摊是因为 resize 不是常数，而是线性的。考虑一次 resize 所对应的 N 的变化，可以把这个线性均摊到若干次引发 N 变化的 push 中，而且可以计算出均摊后的常数

[Higurashi]

@lance6716 #1 感谢回复。是的，但不知道下面的理解是哪里出了问题：

比如 N 为 32 ，Stack 将在第 33 次 push() 操作时数组长度从 32 resize() 到 64 ，且此次 resize() 操作对数组的访问次数为 64 ，前一次数组加倍发生在第 17 次 push() 操作，数组长度从 16 resize() 到 32 ，resize() 操作对数组的访问次数为 32 。

那么，按照证明中的说法，对于第 33 次 push()，考虑使栈大小增长到 k 的最近 N/2-1=15 次 push() 操作（其中 k 在 N/2+2=18 到 N=32 之间），这 15 次 push() 操作之间只有一次 resize()，发生在第 17 次 push() 操作时，其访问数组的次数为 32 ，并不等于 4N=128 ，而 15 次 push() 操作，a[N++] = item; 对数组的访问为 15 次，也并不等于 N/2=16 次，更不用说取平均得到 9 。

[lance6716]

那个 4N 除了 resize ，内部的数组访问也要统计，不过这个实际上是想表达缩放之后上界取了 4N 。

“15 次 push”是因为你没有算“第 33 次 push”。

[lance6716]

对了“从矩阵中找极小值”那个题有点问题，已经跟作者反馈了，但是你买的书的话就没法更新了

[Higurashi]

@lance6716 #3 嗯，我从 https://www.cnblogs.com/longjin2018/p/9854502.html 找到了更多的解释：

“设栈长度达到 N/2+1 时数组长度从 N/2 延长至 N 。连续的 push 操作使数组从长度 N 延长至 2N 是最坏的连续 push 情况。栈长度在 N/2+2 至 N 区间进行的 N/2-1 次 push 操作不会促使数组延长，此区间每次 push 对应一次数组元素的写访问。栈长度从 N 变为 N+1 时需要一次 push 操作和一次数组延长，一次 push 操作对应一次数组写操作，一次数组延长对应 4N 次数组访问。那么栈长度从 N/2+1 变为 N+1 需要进行的数组访问次数为 N/2+4N,push 操作次数为 N/2,均摊后每次 push 操作对应的数组访问次数为(N/2+4N)/(N/2)=9 。”