2

動的配列に関するウィキペディアの記事によると、配列の最後での挿入/削除はO(1)であり、中央からの挿入/削除はO(n)です。なぜそれが正確なのですか?

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

ありがとう!

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

配列の最後のメモリアドレスへのポインタが手元にあると思います。そのため、追加操作が高速です。逆に、正確な位置を指定すると(配列の最後であっても)、その位置に挿入することは前述のメモリアドレスを使用することと同じであることがわからないため、配列全体をトラバースする必要があります。

4

5 に答える 5

10

配列の最後に挿入するには、アイテムをそこに配置するだけです。

配列の中央に挿入するには、そのポイント以降のアイテムを1つずつ上に移動する必要があります。

配列の最後から削除するには、その数を1つ減らすだけです。

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

それをO(n)に変えるのはシフトです。

于 2009-05-06T02:13:58.687 に答える
8

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

于 2009-05-06T02:16:49.087 に答える
1

とても簡単です。

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

于 2009-05-06T02:16:47.060 に答える
0

アダムロビンソンの優れた要約に追加する:これは単なる理論ではありません。配列の最後に繰り返し追加することによって動的配列が構築される状況を何度も見てきました。(N**2)配列を繰り返し再割り当てする必要があり、その各メンバーを新しい配列構造にコピーする必要があるため、これはパフォーマンスに影響します。再割り当ては、追加操作の1/10でのみ発生する可能性がありますが、それは十分に悪いことであり、(N**2)パフォーマンスの面でも問題はありません。

vector::reserve(N)STLでは、ベクトルに書き込む前に呼び出すことで、このパフォーマンスの低下を回避できます。しかし、そのステップは見過ごされがちです。

于 2009-05-06T02:36:37.213 に答える
-2

実際、それはBig-OではなくBig-Thetaです。

于 2009-05-06T02:18:21.627 に答える