了解摊销时间和数组插入为O(1)的原因 [英] Understanding Amortized Time and why array inserts are O(1)

问题描述

我正在读破解编码采访，在Big O一章中，有一个关于摊销时间的解释。这里使用了需要增长的ASN ArrayList等内容的经典示例。当数组需要增长时，假设必须将N个元素复制到新的Array，插入将花费O(N)时间。这很好。

我不明白的是，数组容量翻了一番，为什么每次插入的摊销时间，从我了解的情况来看，任何时候插入到数组，都是O(N)操作。摊销时间有什么不同？我确信文本是正确的，我只是不理解O(1)摊销时间概念。

推荐答案

我正在回答您似乎感到困惑的问题，而不是您正式提出的问题。

您真正的问题是如何进行O(1)追加操作。如果已经为数组的下一个元素分配了空间，那么追加只是更新有多少元素在其中的记录，并复制条目。这是O(1)操作。

如果溢出可用空间，则仅追加是很昂贵的。然后，您必须分配更大的区域，移动整个数组，并删除前面的数组。这是O(n)操作。但如果我们仅每O(1/n)次执行一次，则平均仍可得出O(n * 1/n) = O(1)次。

平均数是否重要取决于您的任务。如果你在控制重型机械，在单个操作上花费太长时间可能意味着你不能足够快地回到旋转叶片上，这在官方看来是不好的。如果您正在生成网页，那么最重要的是一系列操作所花费的总时间，也就是操作次数乘以每个操作的平均时间。

对于大多数程序员来说，平均数才是最重要的。

这篇关于了解摊销时间和数组插入为O(1)的原因的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！