在谈到算法的时间复杂性时,“恒定摊销时间”是什么意思?
摊销时间用简单的术语解释:
如果您执行一百万次操作,那么您实际上并不关心该操作的最坏情况或最佳情况-您所关心的是,重复一百万次操作总共要花费多少时间。
因此,如果操作偶尔会非常缓慢,则无关紧要,只要“偶尔执行一次”足够稀少,就可以将缓慢性冲淡掉。本质上,摊销时间是指“如果执行多次操作,则平均每次操作花费的时间”。摊销时间不必恒定。您可以使用线性和对数摊销时间或其他方式。
让我们以动态数组为例,向其重复添加新项目。通常,添加项目需要固定的时间(即O(1))。但是,每次阵列满时,您将分配两倍的空间,将数据复制到新区域中,并释放旧空间。假设分配和释放以恒定的时间运行,则此扩展过程将花费一些O(n)时间,其中n是数组的当前大小。
O(1)
O(n)
因此,每次放大时,您花费的时间是上一次放大时的两倍。但是您也已经等待了两倍的时间!因此,每次扩大的成本可以在插入物之间“摊开”。这意味着从长远来看,将 m个 项目添加到数组所需的总时间为O(m),因此摊销时间(即每次插入的时间)为O(1)。
O(m)