私は最近、Java から ArrayList を読んでいました。私の理解では、ArrayList がその容量に達すると、サイズ変更メソッドが呼び出され、元のサイズの2 倍の新しい基になる配列が作成されます。この場合、挿入は O(n) と見なすことができますが、平均的には O(1) のままです。ただし、具体的に2倍のサイズに増加した理由については混乱しています。元の容量の3倍に増やしたほうがいいでしょうか？
私は最近、Java から ArrayList を読んでいました。私の理解では、ArrayList がその容量に達すると、サイズ変更メソッドが呼び出され、元のサイズの2 倍の新しい基になる配列が作成されます。この場合、挿入は O(n) と見なすことができますが、平均的には O(1) のままです。ただし、具体的に2倍のサイズに増加した理由については混乱しています。元の容量の3倍に増やしたほうがいいでしょうか？