1

Linked List の複雑さの大部分は理解しています。アイテムへのアクセスは、最後にあるか存在しない可能性があるため、最悪の場合 O(n) です。ソートされていないリンク付きリストへの追加は O(1) です。これは、ヘッダーとして追加できるためです。

しかし、配列の場合、私は混乱しています。アクセスがいかに効率的であるか (O(1)) について多くのことを読みましたが、追加は必ずしも必要ではなく、削除もそうで​​はありません。どうしてこれなの？

足し算がいつも最後じゃないから？O(1) ですよね？しかし、それが別の時点にある場合は、アイテムをシフトする必要があります。これは O(n) でしょうか? そして、これは高級言語で言えば「舞台裏」で行われていますよね？メモリの場所を移動していて、そこから複雑さが始まるのですか?

削除するとギャップが発生しますか? そして、それを埋める必要がありますか？

基本的に、10 個の項目を含む配列があり、5 番目のインデックス ポイントに項目を追加する場合、すべての項目をインデックス 5 以上から 1 つ上のインデックス ポイントにコピーする必要があり、操作がO(n)?

明確化をいただければ幸いです。

4

2 に答える 2

2

（たとえば、配列の真ん中に）挿入するのはO(n)、あなたが述べたように、後続のすべての要素を右に移動する必要があるためです。したがって、最初の位置に挿入するnと、既存の要素をすべて移動して場所を空ける必要があり、最悪の場合のコストはn. 平均して、ランダムな位置に挿入すると仮定すると、(n/2)要素を移動しています。

（配列の最後に）追加するのもO(n)、再割り当てが必要なためです。配列が、配列の現在のサイズよりも大きくなるように割り当てられたメモリのチャンクに存在する場合、これは問題ではありません。メモリ内の次の場所に（一定時間）書き込むだけです。しかし、最終的にあなたは部屋を使い果たすつもりです。次に、より大きなメモリの新しい塊を割り当て、既存のすべての要素をそこにコピーする必要があります。したがって、最悪の場合の正味コストはn+1(nコピー数 +1追加) であり、O(n). (メモリを割り当てるために発生する舞台裏のコストもあります。) このコストを回避するために、多くの言語とライブラリでは、配列内にスペースを事前に割り当てて、配列内で見られると予想される要素の最大数をカバーするオプションを提供しています。あなたの申請; これにより、予想される数よりも多くの要素を追加しない限り、再割り当てが行われないことが保証されます。

削除はO(n)、（あなたが言うように）削除された要素の後のすべてを1スペース左に戻す必要があるためです。n-1最初の位置から削除すると、残りのすべての要素を移動する必要がありO(n)、最悪の場合に備えます。（最後の位置から削除すると、一定の時間がかかります。）

于 2013-01-13T17:53:57.187 に答える
1

通常、配列は固定長のデータ構造です。この特性には、長所と短所があります。

リンクされたリストと比較した配列の利点は、配列内の位置がわかっている場合、Θ(1) で配列内の任意の項目にアクセスできることです。配列内のアイテムの内部順序に応じて、特定の値の検索は非常に効率的です。たとえば、アイテムがソートされた順序になっている場合、配列内の二分探索でΟ(log n ) だけが必要になります。線形アクセスを必要とする連結リストの場合はΟ( n )。

配列の主な欠点は、配列のサイズを変更する必要がある場合、すべてのアイテムをコピーする必要があることです。したがって、配列にギャップが必要ない場合は、挿入および削除操作に Θ( n ) が必要です。

于 2013-01-13T18:27:33.547 に答える