java - 当我们为数组重新分配内存时，可扩展数组会做什么？

Question

我刚刚遇到这个问题，如果我们有一个动态分配的数组，则插入需要 O(1) 。但是当数组已满时，我们需要为数组重新分配双倍空间，因此复制旧数组需要 O(n)。

有什么办法可以使它成为 O(1)？

我读过一些关于可扩展数组的文章，但我并不理解它。任何人都可以帮助解释更多吗？

非常感谢。

Answer 1

每次分配两倍的空间形成几何级数。这意味着虽然一些插入（触发扩展的插入）非常昂贵，但它们非常罕见，以至于摊销性能仍然是 O(1)。例如，插入十亿个元素只需要 30 次加倍 (2^30=1,073,741,824)。