摊销分析的基本问题
Fundamental question of amortized analysis
一个数据结构支持一个操作 foo 使得 n 个操作 foo 的序列在最坏的情况下需要 Θ(n log n) 时间来执行。
a) What is the amortized time of an foo operation?
b) How large can the actual time of a single foo operation be?
a) 首先我假设 foo 是 O(log n) 最坏的情况。
因此，摊销成本来自 foo 讲述其最坏情况的频率。由于我们一无所知，因此摊销在 O(1) 和 log n
之间
b) O(log n)
这是正确的吗？在这里争论的正确方式是什么？
a) 如果 n 操作需要 Θ(n log n)，那么根据定义，foo 操作的摊销时间是 Θ(log n) 摊销时间是所有操作的平均值，因此您不会仅将最坏的情况与导致它的操作进行计算，但也会对所有其他情况进行摊销。
b) foo 偶尔会花费 O(n)，只要不超过 O(log n) 次。 foo 甚至偶尔会花费 O(n log n)，只要这种情况发生的次数不超过常量（即 O(1)）。
进行摊销分析时，不会将最坏情况乘以操作次数，而是乘以最坏情况实际发生的次数。
例如，采取将元素一次一个地推入向量的策略，但每次新元素不适合当前分配时，通过将分配的大小加倍来增加内存。每个加倍实例的成本为 O(n)，因为您必须 copy/move 所有当前元素。但摊销时间实际上是线性的，因为您复制了 1 个元素一次、2 个元素一次、4 个元素一次，等等：总的来说，您已经完成了 log(n) 倍增，但每个成本的总和只是 1+2+4+8+...+n = 2*n-1 = O(n)。所以这个 push 实现的摊销时间是 O(1)，即使最坏的情况是 O(n).
一个数据结构支持一个操作 foo 使得 n 个操作 foo 的序列在最坏的情况下需要 Θ(n log n) 时间来执行。
a) What is the amortized time of an foo operation?
b) How large can the actual time of a single foo operation be?
a) 首先我假设 foo 是 O(log n) 最坏的情况。 因此，摊销成本来自 foo 讲述其最坏情况的频率。由于我们一无所知，因此摊销在 O(1) 和 log n
之间b) O(log n)
这是正确的吗？在这里争论的正确方式是什么？
a) 如果 n 操作需要 Θ(n log n)，那么根据定义，foo 操作的摊销时间是 Θ(log n) 摊销时间是所有操作的平均值，因此您不会仅将最坏的情况与导致它的操作进行计算，但也会对所有其他情况进行摊销。
b) foo 偶尔会花费 O(n)，只要不超过 O(log n) 次。 foo 甚至偶尔会花费 O(n log n)，只要这种情况发生的次数不超过常量（即 O(1)）。
进行摊销分析时，不会将最坏情况乘以操作次数，而是乘以最坏情况实际发生的次数。
例如，采取将元素一次一个地推入向量的策略，但每次新元素不适合当前分配时，通过将分配的大小加倍来增加内存。每个加倍实例的成本为 O(n)，因为您必须 copy/move 所有当前元素。但摊销时间实际上是线性的，因为您复制了 1 个元素一次、2 个元素一次、4 个元素一次，等等：总的来说，您已经完成了 log(n) 倍增，但每个成本的总和只是 1+2+4+8+...+n = 2*n-1 = O(n)。所以这个 push 实现的摊销时间是 O(1)，即使最坏的情况是 O(n).