使用堆栈的摊余成本分析
Amortized Cost Analysis with a Stack
假设我有一个由 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)
我觉得一切都很合理：
1) 让我们从一个空栈开始，用一个初始大小为 n=1
的数组表示
- push 1. element =>
cost = <push-cost> = 1 => array now full
- 推送 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
...等等，这确实导致在推送 n 元素时总成本为 1 + 2 + 3 + ... + n。
2) 你没有说你的文字是怎么说这个行为的，但是计算是相似的：
- push 1. element =>
cost = <push-cost> = 1 => array now full
- 推送 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 => array now full
- 推送 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 => array now full
- 推 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 "resize-free" 操作。因此，我们可以将其重写为 (collapse + 1-chains to the left)
1 + 2 + 4 + 8 + 16 + ...
（非正式地）表示每个推送操作的总成本 O(n) 或摊销成本 O(1)。
假设我有一个由 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)
我觉得一切都很合理：
1) 让我们从一个空栈开始，用一个初始大小为 n=1
- push 1. element =>
cost = <push-cost> = 1=> array now full - 推送 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
...等等，这确实导致在推送 n 元素时总成本为 1 + 2 + 3 + ... + n。
2) 你没有说你的文字是怎么说这个行为的，但是计算是相似的：
- push 1. element =>
cost = <push-cost> = 1=> array now full - 推送 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=> array now full - 推送 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=> array now full - 推 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 "resize-free" 操作。因此，我们可以将其重写为 (collapse + 1-chains to the left)
1 + 2 + 4 + 8 + 16 + ...
（非正式地）表示每个推送操作的总成本 O(n) 或摊销成本 O(1)。