我正在阅读《破解编码面试》，在 Big O 章节中，有关于摊销时间的解释。这里使用了 ArrayList 等需要增长的经典示例。当数组需要增长时，插入将花费O(N)假设必须将 N 个元素复制到新数组所需的时间。这可以。
我不明白的是，随着数组容量加倍，为什么每次插入的摊销时间会是O(1)据我所知，每当你插入数组时，它总是一个O(N)手术。摊销时间有何不同？我确信文字是正确的，我只是没有理解O(1)摊销时间概念。
我正在回答您似乎感到困惑的问题，而不是您正式提出的问题。
你真正的问题是如何附加O(1)手术。如果已经为数组的下一个元素分配了空间，那么追加只是更新有多少元素的记录，并复制该条目。这是一个O(1)手术。
如果可用空间溢出，则仅追加会很昂贵。然后你必须分配一个更大的区域，移动整个数组，并删除以前的。这是一个O(n)手术。但如果我们只是每次都这样做O(1/n)次，然后average它仍然可以出来O(n * 1/n) = O(1).
平均值是否重要取决于您的任务。如果您控制重型机械，在单个操作上花费太长时间可能意味着您无法足够快地返回到旋转刀片，这可能会很糟糕。如果您要生成网页，那么重要的是一系列操作所花费的总时间，即操作次数乘以每次操作的平均时间。
对于大多数程序员来说，平均水平才是最重要的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
