一个数据结构支持一个操作 foo，这样在最坏的情况下，一系列 n 个操作 foo 需要Θ(n log n)时间来执行。
a) foo 操作的摊销时间是多少？
b) 单个 foo 操作的实际时间可以有多大？
a）首先我假设 foo 是 O(log n) 最坏的情况。因此，摊销成本来自于 foo 讲述其最坏情况的频率。由于我们一无所知，因此摊销介于 O(1) 和 log n 之间
b) O(log n)
它是否正确？在这里争论的正确方法是什么？
问问题
82 次
1 回答
2
a) 如果n操作采取Θ(n log n)，那么根据定义，一个foo操作Θ(log n)的摊销时间是 摊销时间是所有操作的平均值，所以你不要只计算导致它的操作的最坏情况，而是对所有其他操作进行摊销，也。
b)foo偶尔会花费O(n)，只要不超过O(log n)次。foo有时甚至可能会花费O(n log n)，只要这种情况发生的次数不超过恒定（即O(1)）次数。
当您进行摊销分析时，您不会将最坏情况乘以操作次数，而是乘以最坏情况实际发生的次数。
例如，采用一次将元素推入向量的策略，但每次新元素不适合当前分配时，通过将分配的大小加倍来增加内存。O(n)由于您必须复制/移动所有当前元素，因此每个实例的成本翻倍。但摊销时间实际上是线性的，因为您复制 1 个元素一次、2 个元素一次、4 个元素一次等：总体而言，您已经完成了log(n)翻倍，但每项成本的总和仅为1+2+4+8+...+n = 2*n-1 = O(n). 所以这个push实现的摊销时间是O(1)，即使最坏的情况是O(n)。
于 2019-08-13T04:42:57.897 回答