動的配列O（1）の最後に挿入するのにO（n）を挿入するのはなぜですか？

Question

動的配列に関するWikipediaの記事によると、最後に挿入/削除配列はO（1）であり、中央からの挿入/削除はO（n）です。なぜ正確なのですか？

また、5つの要素を持つ動的配列があり、位置6に新しい要素を挿入する場合、操作はO（n）であり、関数を使用して配列の最後に追加する場合はO（1）です。どちらの場合でも配列のサイズを変更する必要がないと仮定すると、これは同じ操作ではありませんか？または、動的配列に追加すると、実際に位置6以外の場所に新しい要素が挿入されますか？

ありがとう！

編集：主な混乱は、配列の最後に挿入することと、配列の最後に相当する特定の位置に挿入することの違いだと思います。

配列の末尾のメモリアドレスへのポインタが便利に保たれているため、追加操作が速いのはこのためです。逆に、正確な位置を指定した場合（配列の最後であっても）、その位置に挿入することは前述のメモリアドレスを使用することと同じであることが分からないため、配列全体をトラバースする必要がありますか？

Answer 1

マグニチュードの順序は、「動的配列」のデータ構造の種類に完全に依存します。実際は（「動的配列」は厳密に定義されたデータ構造ではなく、特定のデータ構造を使用することで達成される望ましい結果です）。あなたが与える例は、リンクされたリストを採用することによって達成される動的な配列によって反映されるでしょう。リスト構造が最終要素へのポインタを保持している場合、最後に追加するとO（1）になる可能性があります。 （インデックスに関係なく）挿入するには、リンクリストをトラバースする必要があります。つまり、目的のインデックスまでノードごとに1つの操作が必要です。

Answer 2

配列の最後に挿入するには、そこに項目を配置するだけです。

配列の中央に挿入するには、そのポイントの後に項目を1つ上に移動する必要があります。

配列の末尾から削除するには、そのカウントを1つドロップします。

中央から削除するには、それを行う必要があり、 他のアイテムを下にシフトします。

O（n）に変換するのは shifting です。

Answer 3

非常に簡単です：

中央に挿入するには、後の各要素を1つずつ移動します。 最後に挿入するために、追加のスペースが予約されている場合、アイテムはそこに保存されますが、そうでない場合は新しいスペースが割り当てられます。したがって、この操作は償却後一定時間で行われます。

Answer 4

Adam Robinsonの優れた要約に追加：これは単なる理論ではありません。配列の末尾に繰り返し追加することにより、動的配列が構築される状況を何度も見てきました。これはo （N ** 2）のパフォーマンスになります。これは、配列を繰り返し再割り当てする必要があるため、各メンバーが新しい配列構造に強制的にコピーされるためです。再割り当ては、追加操作の1/10でのみ発生する可能性がありますが、それは十分に悪いことであり、パフォーマンスに関しては依然として（N ** 2）です。

STLでは、ベクターに書き込む前に vector :: reserve（N）を呼び出すことにより、このパフォーマンスの低下を回避できます。しかし、そのステップはしばしば見落とされます。

Answer 5

実際には、Big-Oではなく、 Big-Theta 。