0

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

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

1 + 2 + 3 + ... + n

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

我推送，堆栈现在已满（成本 1）我增加数组的大小（n = 2 和成本 2）我推送并且堆栈现在已满（成本 1）我增加数组的大小（n = 3 和成本4) ...

我错过了什么？

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

我推送，堆栈现在已满（成本为 1）我将数组大小加倍并复制 1 个元素（成本为 2，n = 2）我推送并且堆栈现在已满（成本为 1）我将数组大小加倍并复制 2元素超过（成本 4，n = 4）...

这个分析看起来对吗？

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

4

1 回答 1

2

一切对我来说都是合理的：

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

  • push 1. element => 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）你没有说你的文字对这种行为说了什么，但计算是相似的：

  • push 1. element => 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
  • push 4. element => 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
  • push 8. element => 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“无调整大小”操作。因此，我们可以将其重写为 (collapse + 1-chains to the left)

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

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

于 2015-08-30T23:18:24.337 回答