我正在阅读Cracking the Coding Interview,在Big O一章中,有关于Amortized Time的解释。此处使用了需要增长的诸如 ArrayList 之类的经典示例。当一个数组需要增长时,O(N)
假设它必须将 N 个元素复制到新数组中,插入将需要时间。这可以。
我不明白的是,由于数组的容量增加了一倍,为什么每次插入的摊销时间会O(1)
根据我的理解,无论何时插入数组,它总是一个O(N)
操作。摊销时间有何不同?我确定文字是正确的,我只是不理解O(1)
摊销时间的概念。