命题。在 Stack 的大小调整数组实现中，从空数据结构开始的任何操作序列的平均数组访问次数在最坏的情况下是恒定的。
证明草图：对于导致数组增长的每个 push()（例如从大小 N 到大小 2N），考虑N/2 - 1最近导致堆栈大小增长到 k 的 push() 操作，对于 k 从N/2 + 2 to N. 平均 4N 次数组访问以通过 N/2 次数组访问（每次推送一次）来增长数组，我们得到每个操作的平均 9 次数组访问成本。证明任何 M 操作序列使用的数组访问次数与 M 成正比更加复杂。（算法第 4 版第 1.4 章）
我不完全理解证明草图。请帮助我理解这一点。
我认为这是一种摊销分析，在这种分析中，您向诸如 push() 之类的请求收取并非直接归因于它们的工作，然后表明没有人必须支付过高的账单，这意味着完成工作的平均成本是小的。
在这种情况下，当空间不足时，您必须复制整个数组，但这样做时会将大小翻倍，因此您不会经常复制 - 例如大小为 1、2、4、8、16.. . 在这里，我们将每个数组副本计入自上次数组副本以来已完成的 push() 操作。这意味着如果除了 push() 之外什么都不做，那么每个 push() 只获取在它之后发生的第一个数组副本的账单，所以如果账单（拆分为多个 push() 操作）每次推送都很小（ ) 那么摊余成本很小。
如果数组在空间用完并且大小翻倍之前的大小为 N，那么本文说这需要 4N 次操作，这听起来很合理，而且我们不太关心常数因子。自上次加倍以来，这将被拆分为所有操作。最后一次翻倍是从尺寸 N/2 到尺寸 N，所以大约有 N/2 个。这使您在 N/2 push() 操作上拆分了 4N 个操作，因此每次推送都会共享 8 个账单。不要忘记 push() 涉及数组写入，无论它是否触发大小加倍，并且您会得到一个每次 push() 的平均写入成本为 9 次。