为堆栈大小调整阵列平摊分析 [英] Amortized Analysis for Re-sizing Array for Stack

问题描述

命题。在调整大小的数组实现栈， 阵列的平均数目为操作从开始任何顺序访问 一个空的数据结构是，在最坏的情况下恒定

Proposition . In the resizing array implementation of Stack, 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），审议 N / 2 - 1 推（）操作，以最近引起 堆栈大小将增长到K，对于k从 N / 2 + 2到N 。平均的4N数组访问 成长与N / 2数组访问阵列（每个推送），我们得到一个平均成本 9阵列的每个操作的访问。证明阵列的存取次数使用的 中号操作的任何序列成正比M是更复杂的。 （算法第4版第1.4章）

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. Proving that the number of array accesses used by any sequence of M operations is proportional to M is more intricate. (Algorithms 4th Edition Chapter 1.4)

我不明白的证明素描完全。请帮我在得到这个理解。

I didn't understand the Proof Sketch Completely. Please help me in getting this understand.

推荐答案

我觉得这是有点摊销分析，你的工作就像充电推送请求（）不直接由于它们，然后显示，没有人支付过高的法案，这意味着工作的平均成本做得很小。

I think this is sort of amortized analysis where you charge requests like push() for work that isn't directly due to them, and then show that nobody has to pay too high a bill, which means that the average cost of work done is small.

在这种情况下，你有当您运行的空间来复制整个数组，但你双倍的大小，当你做到这一点，所以你不要复制很多时候 - 如在尺寸1，2，4，8，16 ...在这里，我们开帐单每个阵列拷贝给推送（）操作自上次阵列复制已完成。这意味着，如果你做什么，但推（），然后每按（）获取该法案仅适用于后发生的第一阵列复制，因此，如果该法案（拆过一些推（）操作）为每推小（ ），那么摊余成本是很小的。

In this case you have to copy the entire array when you run out of space, but you double the size when you do this, so you don't copy very often - e.g. at size 1, 2, 4, 8, 16... Here we bill each array copy to the push() operations which have been done since the last array copy. This means that if you do nothing but push() then each push() gets the bill only for the first array copy that occurs after it, so if the bill (split over a number of push() operations) is small per push() then the amortized cost is small.

如果数组为N个大小为它运行的空间之前和尺寸得到翻倍，那么这篇文章说，这个费用4N操作，这听起来很有道理，我们不在乎多少常数因子反正。这被拆分为自去年翻了一番所有操作。最后的倍增是从尺寸N / 2到大小为N因此大约有N / 2人。这可以让你4N OPS拆分成N / 2推（）操作，这样每个推得到的8共享法案不要忘了，一推（）涉及到一个数组写是否触发尺寸增加一倍，你会得到一个每推9平均成本写（）。

If the array is of size N before it runs out of space and gets doubled in size then this article says this costs 4N operations, which sounds reasonable, and we don't care about constant factors much anyway. This gets split over all the operations since the last doubling. The last doubling was from size N/2 to size N so there are about N/2 of them. This gets you 4N ops split over N/2 push() operations so each push gets a shared bill of 8. Don't forget that a push() involves an array write whether or not it triggers a size-doubling and you get an average cost of 9 writes per push().

这篇关于为堆栈大小调整阵列平摊分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！