重新调整数组大小的摊销分析用于栈

Question

重新调整数组大小的摊销分析用于栈

3

命题：在栈的调整大小数组实现中，从空数据结构开始的任何操作序列的平均数组访问次数在最坏情况下是恒定的。 证明草图：对于每个导致数组增长的push()（比如从大小N增长到大小2N），考虑最近导致堆栈大小增长到k的N/2-1个push()操作，其中k从N/2+2到N。将4N个数组访问扩展为N/2个数组访问（每个push一个），我们得到每个操作的平均成本为9个数组访问。证明M个操作使用的数组访问次数与M成比例更加复杂。（算法第四版第1.4章）

我没有完全理解证明草图。请帮助我理解。

- mohit

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

我认为这是分摊分析，其中您会对像push()这样的请求收费，即对并非直接与它们相关的工作进行收费，然后表明没有人需要支付太高的账单，这意味着完成的工作的平均成本很小。

在这种情况下，当空间用尽时，必须复制整个数组，但是当您这样做时，您会将大小加倍，因此您不经常进行复制-例如在大小为1、2、4、8、16 ... 在这里，我们将每个数组副本都计入自上次数组副本以来已完成的push()操作。这意味着，如果您只进行push()操作，则每个push()仅获得其之后发生的第一次数组副本的账单，因此，如果每个push()操作的账单（在多个push()操作中拆分）较小，则分摊成本也很小。

如果数组在耗尽空间并增加一倍大小之前的大小为N，则本文称这将花费4N个操作，这听起来很合理，我们不太关心常数因子。这些操作分散在自上次加倍以来的所有操作中。最后一次加倍是从大小N/2到大小N，因此大约有N/2个加倍。这样，4N个操作就可以分配到N/2个push()操作中，因此每个push()都要分摊8个操作。不要忘记，无论是否触发了大小加倍，push()都涉及数组写入，并且您平均每个push()需要9次写入。