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