我只是想在继续之前与某人确认我在正确的轨道上。问题指出，当我想向已经满的数组添加新元素时，我必须“以 O(1)（摊销）扩展数组”。
这是说每次我将一个新元素插入一个完整列表时，我应该添加 5 个元素或类似的东西，这样我就不必在每次添加新元素时执行扩展？
这是说每次我将一个新元素插入一个完整列表时，我应该添加 5 个元素或类似的东西，这样我就不必在每次添加新元素时执行扩展？
有点。但是任何固定数量的额外槽都会有同样的问题：即使你只需要每五次插入复制到一个新数组，每次插入的平均时间仍然是 O( n )，因为 O( n / 5 ) = O ( n )。
相反，您需要添加与数组当前大小成比例的槽数。最简单的方法是在需要增长时将数组大小加倍，平均为 O( n / n ) = O(1); 但是将其增加（例如）50% 或任何其他恒定比例，都会产生相同的效果。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句