algorithm - 使用堆栈的摊余成本分析

Question

假设我有一个由 n 元素数组支持的堆栈，压入成本为 1，从数组中取出元素的成本为 1，调整数组大小的成本是移动的元素数。

1) 每次堆栈变满时，我将当前的 n 个元素复制到一个比以前大一个元素的新数组中。我的文字声称一系列 n 次推送将导致总成本为:

1 + 2 + 3 + ... + n

这是为什么？假设我的数组从 n = 1 开始。

我插入，现在堆栈已满(成本 1)我增加数组的大小(n = 2 和 2 的成本)我推，堆栈现在已满(1 的成本)我增加数组的大小(n = 3 和 4 的成本)...

我错过了什么？

2) 假设每次堆栈满时我都将数组的大小加倍。现在我有一系列 n 推送，从一个 1 元素数组开始:

我按下，堆栈现在已满(1 的成本)我将数组大小加倍并复制 1 个元素(2 的成本，n = 2)我推，堆栈现在已满(1 的成本)我将数组大小加倍并复制 2 个元素(4 的成本，n = 4)...

这个分析看起来正确吗？

对于一系列的 n 次推送，它将产生 1 + 2 + 1 + 4 + 1 + 8 + ... + 1 + 2 ^ (n/2)

Answer 1

我觉得一切都合理:

1) 让我们从一个空栈开始，用一个初始大小为 n=1 的数组表示

• 推 1. 元素 => cost = <push-cost> = 1 => 数组现在已满
• 推 2. 元素 => cost = <resize-cost> + <push-cost> = n + 1 = 2 => n := n + 1 = 2
• 推 3. 元素 => cost = <resize-cost> + <push-cost> = n + 1 = 3 => n := n + 1 = 3

...等等，这确实导致总成本为 1 + 2 + 3 + ... + n推的时候n元素。

2) 你没有说出你的文字对这种行为的看法，但计算是相似的:

• 推 1. 元素 => cost = <push-cost> = 1 => 数组现在已满
• 推 2. 元素 => cost = <resize-cost> + <push-cost> = n + 1 = 2 => n := 2 * n = 2
• 推 3. 元素 => cost = <resize-cost> + <push-cost> = n + 1 = 3 => n := 2 * n = 4
• 推 4. 元素 => cost = <push-cost> = 1 => 数组现在已满
• 推 5. 元素 => cost = <resize-cost> + <push-cost> = n + 1 = 5 => n := 2 * n = 8
• 推 6. 元素 => cost = <push-cost> = 1
• 推 7. 元素 => cost = <push-cost> = 1
• 推 8. 元素 => cost = <push-cost> = 1 => 数组现在已满
• 推 9. 元素 => cost = <resize-cost> + <push-cost> = n + 1 = 9 => n := 2 * n = 16

...这导致总成本为

1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 + 9 + 1 + 1 + 1 + 1 + 1 + 1 + 1...

请注意调整大小操作总是发生在元素 2^n+1 上, 其次是 2^n-1 “无调整大小”操作。因此，我们可以将其重写为(向左折叠 + 1 -链)

1 + 2 + 4 + 8 + 16 + ...

(非正式地)表示 O(n) 的总成本或 O(1) 的摊余成本每次推送操作。