リンクリストへの挿入の時間計算量

Question

この質問が解決策の検証のように感じられた場合は申し訳ありませんが、この質問は私の大学院入学試験で尋ねられたものであり、これに多くのことが当てはまります。

挿入の最悪の場合の時間の複雑さはどれくらいですか $n$ リンク リストをソート順に維持する必要がある場合、要素を空のリンク リストに追加しますか?

私の意見では、答えは次のようになります。 $O(n^2)$ なぜなら、挿入するたびに要素を正しい場所に挿入する必要があり、すべての要素を最後の場所に挿入する必要がある可能性があるため、時間の計算量は次のようになります。 1 ドル + 2 ドル + ...(n-1) + n = O(n^2)$

ただし、私が持っている解決策は、最初に要素を並べ替えることができると言っています $O(n \log n)$ 次に、それらを 1 つずつ挿入します。 $O(n)$, 、全体的な複雑さは次のようになります。 $O(n \log n)$.

質問の与えられた文言から、どの解決策がより適切ですか?私の意見では、質問では「リンクされたリストはソートされた順序で維持する必要がある」と述べられているため、要素を事前にソートしてからソートされた順序で挿入することはできないと言いたいと思います。

Answer 1

質問では、ターゲットリストをソート順に維持する必要があるとだけ述べています。使用することを選択できる他のデータ構造については何も述べていません。提案された解決策は、まず挿入する引数の前処理を行ってから、適切な挿入を行います。これは問題ステートメントで許可されています。

要素を挿入してから並べ替えるのではなく、これを行う実際的な理由は、リンク リスト オブジェクトが常に並べ替えを必要とする別のスレッドと共有されている場合です。(そのようなシナリオでは、1 つの要素の挿入がアトミックであることを確認する必要があります。) つまり、この質問は、奇妙にするために奇妙な要件を設けているだけではありません。これは、プログラミングの現実の世界でよく出てくる種類の要件です。

同じ複雑さの別の解決策は、要素が到着したときにターゲット リストに要素を挿入し、要素の値をターゲット リスト内のノード ポインタにマッピングする並列データ構造を維持することです。各要素を挿入するには、マッピング内で前の要素を見つけて、このノードの後に​​新しい要素を挿入します。これは、挿入プロセスが進行中に (既存の空白ノードを埋めるのではなく) リスト ノードを作成することを前提としています。

この質問はアルゴリズムに関するものではなく、読解に関するものです。言い方としては、ちょっとしたひっかけ質問です。正確な読み取りに依存しているため、表現がやや不十分ですが、挿入する要素を取得するにはコストがかかるという事実など、いくつかの重要な前提が述べられていません。 $O(n)$, 、2 つの要素の比較は次のように行うことができます。 $O(1)$, であり、入力ドメインは実質的に制限がありません (演習:を思いつきます $O(n)$ 入力が範囲内の整数の場合のアルゴリズム $[1,42]$）。しかし、与えられた答えは正しいです。

補助データ構造を使用する方法はないと仮定しました。問題文には補助データ構造の使用を禁止するものはありません。補助データ構造を禁止する簡単な方法は、次のようにすることです。 $O(1)$ メモリのオーバーヘッド。

この仮定の下でも、あなたの推論は間違っているか、少なくとも不正確であることに注意してください。要素が正しい順序で与えられていることがたまたまわかっている場合は、リストの末尾へのポインターを保持し、そこに挿入し続けることができます。 $O(n)$. 。最悪のケースは、すべての要素をターゲット リストの最後の位置に挿入する必要がある場合ではなく、何らかの方法でリストをトラバースするときに到達した最後の位置に挿入する必要がある場合です。最悪のケースは確かに $\シータ(n^2)$, しかし、これを証明するには、リスト内の挿入ポイントを見つけるのに時間がかかることを証明する必要があります。 $\シータ(n)$ これには、からの距離を証明する必要があります。 どれでも リストへのポインタは以下によって制限されます $\オメガ(n)$. 。定数がある場合はこれに当てはまります $A$ ポインターの数 (暗黙的に仮定した) $A=1$, 、リストの先頭に単一のポインターがあります)。したがって、少なくともトラバースする必要があります 千ドル/オーストラリアドル 後のノード $k$ 最悪の場合挿入。

Answer 2

私が知っている可能性のある構造は、フィボナッチ山のヒープで、 $ o（1）$ に要素を挿入し、 $ O（\ log（n））$ 、これは $ o（n \ log）の並べ替えを行う場合があります。（n））$ 新しい要素の挿入費用だけ $ o（1）$ 、私はこれに続くことができる他の構造を知っていません。

Answer 3

それは本当にトリッキーな質問です。まず第一に、O（nlogn）の複雑さは、それらの要素間の比較を使用するアルゴリズムのみに適用されます（比較アルゴリズム）。それらの複雑さが、数字をメモリに格納する必要があるビット単位のサイズに依存する基数ソートのような比較例であるアルゴリズムもあります。したがって、私たちがあらゆるアルゴリズムで数字を並べ替えることができると仮定した場合、数字が自然客であり、最大要素はm <10、Radix Sortでは最悪の場合は最悪の場合はO（10n）= O（n）。仮定を任意にすることができないならば、あなたは正しいです。リンクリストリストを使用することができず（任意の種類の索引付けなし）、複雑さはO（N ^ 2）（バブルソート）です。

Answer 4

O（n）であるべきです。 アルゴリズムとして -

に従ってください

1）リンクリストが空の場合は、ノードをそのままにします。 頭を返して戻ってください。

2）挿入するノードの値が小さい場合 ヘッドノードの値よりも、ノードを挿入します 開始時にそれを頭にしてください。

3）ループ内で、後に適切なノードを見つけます 入力ノードを挿入するには。

ヘッドから適切なノードを開始するには、 価値があるノードに到達するまで移動し続けてください 入力ノード。その直前のノードはです 適切なノード

4）適切なノードの後にノードを挿入する ステップ3

で見つかった