摊销分析和一个基本问题（有没有简单的例子）？
amortized analysis and one basic question (is there any simple example)?
我看到两句话：
total amortized cost of a sequence of operations must be an upper
bound on the total actual cost of the sequence
When assigning amortized costs to operations on a data structure, you
need to ensure that, for any sequence of operations performed, that
the sum of the amortized costs is always at least as big as the sum of
the actual costs of those operations.
我的挑战有两点：
A) 它们的意思是：amortized cost >= Real Cost of operation? 我认为摊销是 (n* 实际成本)。
B) 有什么例子可以让我更清楚地理解吗？一个真实而简短的例子？
摊销解决的问题是普通操作可能会偶尔触发慢操作。因此，如果我们把最坏的情况加起来，我们就可以有效地了解如果垃圾收集总是 运行ning 并且每次都必须在内存中移动每个数据结构，程序将如何执行。但是如果我们忽略最坏的情况，我们实际上忽略了垃圾收集有时会 运行，而大列表有时会 运行 超出分配的 space 并且必须移动到更大的桶.
我们通过逐渐注销偶尔的大操作来解决这个问题。一旦我们意识到有一天可能需要它，我们就会立即注销它。这意味着摊销成本通常大于实际成本，因为它包括未来的工作，但有时实际成本比摊销成本大得多。而且，平均而言，它们的结果大致相同。
人们开始使用的标准示例是一个列表实现，我们分配 2x 当前需要的 space，然后在用完 space 时重新分配并移动它。当我在这个实现中 运行 foo.append(...) 时，通常我只是插入。但有时我不得不复制整个大列表。但是，如果我只是复制并且列表中有 n 项，在我 append n 次之后，我将需要将 2n 项复制到更大的 space。因此，我对 append 成本的摊销分析包括插入和移动 2 个项目的成本。在接下来的 n 次我调用 append 时，我的估计值超过了实际成本 n-1 次并且比第 n 次少，但平均结果完全正确。
（Python 的真实列表实现是这样工作的，只是新列表的大小约为旧列表的 9/8。）
我看到两句话：
total amortized cost of a sequence of operations must be an upper bound on the total actual cost of the sequence
When assigning amortized costs to operations on a data structure, you need to ensure that, for any sequence of operations performed, that the sum of the amortized costs is always at least as big as the sum of the actual costs of those operations.
我的挑战有两点：
A) 它们的意思是：amortized cost >= Real Cost of operation? 我认为摊销是 (n* 实际成本)。
B) 有什么例子可以让我更清楚地理解吗？一个真实而简短的例子？
摊销解决的问题是普通操作可能会偶尔触发慢操作。因此，如果我们把最坏的情况加起来，我们就可以有效地了解如果垃圾收集总是 运行ning 并且每次都必须在内存中移动每个数据结构，程序将如何执行。但是如果我们忽略最坏的情况，我们实际上忽略了垃圾收集有时会 运行，而大列表有时会 运行 超出分配的 space 并且必须移动到更大的桶.
我们通过逐渐注销偶尔的大操作来解决这个问题。一旦我们意识到有一天可能需要它，我们就会立即注销它。这意味着摊销成本通常大于实际成本，因为它包括未来的工作，但有时实际成本比摊销成本大得多。而且，平均而言，它们的结果大致相同。
人们开始使用的标准示例是一个列表实现，我们分配 2x 当前需要的 space，然后在用完 space 时重新分配并移动它。当我在这个实现中 运行 foo.append(...) 时，通常我只是插入。但有时我不得不复制整个大列表。但是，如果我只是复制并且列表中有 n 项，在我 append n 次之后，我将需要将 2n 项复制到更大的 space。因此，我对 append 成本的摊销分析包括插入和移动 2 个项目的成本。在接下来的 n 次我调用 append 时，我的估计值超过了实际成本 n-1 次并且比第 n 次少，但平均结果完全正确。
（Python 的真实列表实现是这样工作的，只是新列表的大小约为旧列表的 9/8。）