c++ - 我将如何在 O(1)(摊销)中执行此任务？

Question

我只是想在继续之前向某人确认我走在正确的轨道上。问题指出，当我想向已经满的数组添加新元素时，我必须“在 O(1)(amortized) 中扩展数组”。

这是不是说每次我将一个新元素插入到完整列表中时，我都应该添加 5 个元素或类似的东西，这样我就不必在每次添加新元素时都执行扩展？

Answer 1

Is this saying that every time I insert a new element into a full list that I should add 5 elements or something like that so I don't have to perform an expansion every time a new element is added?

有点。但是任何常量的额外槽都会有同样的问题:即使你只需要每五次插入复制到一个新的数组，这仍然平均为 O(n ) 每次插入的时间，因为 O(ⁿ/₅) = O(n).

相反，您需要添加一些与数组当前大小成比例的槽。最简单的方法是在需要增长时将数组大小加倍，平均为 O(ⁿ/_{n/子>) = O(1);但将其增加(比如)50%，或任何其他恒定比例，也会产生相同的效果。}