ウィキペディアから：
ソートされたリストの実装: スーパーマーケットのレジの列のように、重要な人々が重要でない人々の前で「カット」する場所。( O(n) の挿入時間、O(1) の get-next 時間、O(n*log(n)) のビルド)
二分探索アルゴリズムで挿入位置を検索すると、挿入時間の複雑さは O(log(n)) になるはずです。ここでは、ジョブの到着順序を優先順位の要素として扱います。
それで、私は間違っていますか、それともウィキペディアは間違っていますか?
更新:TAOCP のリストの厳密な定義によると:
線形リストは、n >=0 のノード X 1、X[2]、...、X[n] のシーケンスであり、その基本的な構造特性には、アイテムが行に表示されるときのアイテム間の相対位置のみが含まれます。
ウィキペディアの参照リストはlinked-listではなく、 arrayである可能性があると思います。
ありがとう。
それがリンクされたリストに裏打ちされている場合、バイナリ検索を行うことはできません。挿入ポイントを見つけるのはO(n)です。実際に挿入するのはO(1)です。隣接するノードを変更するだけなので、全体的にO(n)です。
その配列が裏打ちされている場合は、バイナリ検索を実行できます。挿入ポイントの検索は O(log(n)) ですが、配列への挿入は O(n) です。配列のすべての要素をシフトする必要がある場合があるため、全体として O(n)
これが、実際にツリー/ヒープをバックアップして、すべての操作を O(log(n)) できる理由です。
あなたの引用では、ウィキペディアは、ヒープではなく、ソートされたリストに基づく優先キューについて言及しているようです。並べ替えられたリストに項目を挿入するには、O(n) 時間かかります (その並べ替えを維持していると仮定します)。
二分探索は確かにですO(log n)が、二分探索は配列で機能します-O（1）の任意の要素にアクセスできるため、今回は機能します。
ただし、文献では、用語リストを見るときは、リンクリストについて考える必要があります。したがって、リストではO（1）アクセス時間はありませんが、「手動」で位置を検索する必要があります。したがって、要素を挿入するにはO（n）が必要です。
ウィキペディアは正しいです。ここで他の人がすでに述べたように、リストはランダムアクセスではないため、Bに到達する前にAとBの間の各ノードにアクセスする必要があります。リストをトラバースするのはO（n）であるため、バイナリ検索は役に立たなくなります。リストを1回繰り返した場合よりも多くの作業を実行します。開始ノード、中間ノード、および終了ノードを別のバッファーにキャッシュして、最初にそれらをチェックすることができます。ただし、これは複数のリストを使用する場合と同じ効果があります。スキップリストのデータ構造は、そのアイデアをさらに一歩進めます。
したがって、代わりにランダムアクセスヒープを使用するか、必要に応じてスキップリストを使用してください：http： //en.wikipedia.org/wiki/Skip_list 。
ソートされたリストでの最悪の場合の挿入時間は O(n) です。最悪のケースは、最上位の項目をリストに挿入することです。そのためには、すべての要素をステップスルーしてから、最後に挿入する必要があります。バイナリ検索を実行できない理由は、リスト内でアクセスできる要素のみが現在の要素の後継要素であるためです。つまり、ランダム アクセスはありません。