algorithm - 固定摊销时间

Question

在谈到算法的时间复杂性时，“恒定摊销时间”是什么意思？

Answer 1

摊销时间用简单的术语解释:

如果您执行一百万次操作，那么您实际上并不关心该操作的最坏情况或最佳情况-您所关心的是，重复一百万次操作总共要花多少时间。

因此，只要操作偶尔很慢就没关系，只要“偶尔一次”足够稀少就可以将慢速冲淡。本质上，摊销时间是指“如果执行多次操作，则平均每次操作花费的时间”。摊销时间不必恒定。您可以使用线性和对数摊销时间或其他方式。

让我们以动态数组为例，向其反复添加新项目。通常，添加项目需要固定的时间(即O(1))。但是，每次阵列已满时，您将分配两倍的空间，将数据复制到新区域中，并释放旧空间。假设分配和释放以恒定时间运行，则此扩展过程需要O(n)时间，其中n是数组的当前大小。

因此，每次放大时，您花费的时间是上一次放大时的两倍。但是您也已经等待了两倍的时间!因此，每次扩大的成本可以在插入物之间“摊开”。这意味着从长远来看，将m个项目添加到数组所需的总时间为O(m)，因此摊销时间(即每次插入的时间)为O(1)。