algorithm - 摊销成本与最坏情况

Question

我不确定我对摊销分析的理解是否正确。例如，如果我们的摊销成本为 O(1)，并且进行 m 次操作，成本为 O(m)。我们可以说最坏的情况是 m 操作的 O(m)*m 吗？

标签： algorithmamortized-analysis

Answer 1

仅在技术上，因为 m × O(m) = O(m²) 是一个上限而不是下限。

默认情况下，摊销算法从没有信用开始，因此这 m 个操作的实际总运行时间为 Θ(m)，因为信用不能为负数。

由于摊销，对于如何在操作之间分配实际运行时间有很多可能性。你可以有一个操作需要 Θ(m) 实际时间，其余的是 Θ(1)。你可以有 √m 个操作，每个操作都取 Θ(√m)，其余的是 Θ(1)。它们都可能是 Θ(1)。你不能拥有的是总时间 ω(m)。