我正在阅读 Cracking the Coding Interview,在 Big O 章节中,有一个关于 Amortized Time 的解释。这里使用了诸如需要增长的 ArrayList 之类的经典示例。当数组需要增长时,假设必须将 N 个元素复制到新数组,插入将花费 O(N)
时间。这很好。
我不明白的是,由于数组的容量增加了一倍,为什么每次插入的摊销时间都是 O(1)
根据我的理解,任何时候插入数组,它始终是一个 O(N)
操作。摊销时间有何不同?我确信文本是正确的,我只是没有理解 O(1)
摊销时间概念。
最佳答案
我是在回答你似乎困惑的问题,而不是你正式提出的问题。
您真正的问题是追加如何成为 O(1)
操作。如果已经为数组的下一个元素分配了空间,那么追加只是更新其中有多少元素的记录,并复制条目。这是一个 O(1)
操作。
如果溢出可用空间,仅附加是昂贵的。然后你必须分配一个更大的区域,移动整个数组,并删除以前的。这是一个O(n)
操作。但是,如果我们只每 O(1/n)
次执行一次,那么平均它仍然可以达到 O(n * 1/n ) = O(1)
。
平均值是否重要取决于您的任务。如果您正在控制重型机械,在单个操作上花费太长时间可能意味着您不能足够快地回到旋转的 Blade 上,这可能是正式的坏事。如果您要生成网页,那么重要的是一系列操作所花费的总时间,即操作次数乘以每个操作的平均时间。
对于大多数程序员来说,平均值才是最重要的。
关于algorithm - 了解摊销时间以及为什么数组插入是 O(1),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45972160/