O(n) 時間で二重リンク リストのバイナリ検索を実装できると聞いたことがあります。双方向リストのランダムな要素にアクセスするには O(n) 時間がかかり、二分探索は O(log n) 個の異なる要素にアクセスするため、代わりにランタイムを O(n log n) にするべきではありませんか?
13133 次
1 に答える
33
技術的には、二重連結リストでの二分探索の実行時間は O(n log n) であると言うことは正しいですが、それは厳密な上限ではありません。二分探索のわずかに優れた実装とより巧妙な分析を使用すると、二分探索を時間 O(n) で実行することができます。
二分探索の背後にある基本的な考え方は次のとおりです。
- リストが空の場合、検索対象の要素は存在しません。
- さもないと：
- 真ん中の要素を見てください。
- 問題の要素と一致する場合は、それを返します。
- 問題の要素よりも大きい場合は、リストの後半を破棄します。
- 問題の要素よりも小さい場合は、リストの前半を破棄します。
双方向にリンクされたリストでのバイナリ検索の単純な実装は、インデックスを計算して各反復を検索し (配列の場合と同様)、リストの先頭から開始して適切なステップ数。これは確かに非常に遅いです。検索対象の要素が配列の最後にある場合、検索されるインデックスは n/2、3n/4、7n/8 などになります。最悪の場合に実行される作業を合計すると、次のようになります。
n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n) 項)
≥ n / 2 + n / 2 + ... + n / 2 (Θ(log n) 項)
= Θ(n log n)
と
n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n) 項)
≤ n + n + ... + n (Θ(log n) 項)
= Θ(n log n)
したがって、このアルゴリズムの最悪の場合の時間計算量は Θ(n log n) です。
ただし、アプローチをより賢くすることで、これを Θ(log n) の係数で高速化できます。前のアルゴリズムが遅い理由は、要素を検索する必要があるたびに、配列の先頭から検索を開始するためです。ただし、これを行う必要はありません。最初に中央の要素を検索した後、私たちはすでに配列の真ん中にいて、次の検索は n / 4 または 3n / 4 の位置になることがわかっています。中断した場所からの距離 n / 4 (配列の先頭から開始する場合の n / 4 または 3n / 4 と比較して)。リストの先頭から再開するのではなく、停止位置 (n / 2) から次の位置までトレッキングした場合はどうなるでしょうか?
これが私たちの新しいアルゴリズムです。配列の中央までスキャンすることから始めます。これには n / 2 ステップが必要です。次に、配列の前半部分の中央にある要素を訪問するか、配列の後半部分の中央にある要素を訪問するかを決定します。位置 n / 2 からそこに到達するには、合計 n / 4 ステップしか必要ありません。そこから、要素を含む配列の 4 分の 1 の中点に行くには n / 8 ステップしかかからず、そこから要素を含む配列の 8 番目の中点に行くには n / 16 ステップしかかかりません。行われたステップの総数は、
n / 2 + n / 4 + n / 8 + n / 16 + ...
= n (1/2 + 1/4 + 1/8 + ...)
≤ n
これは、無限等比級数 1/2 + 1/4 + 1/8 + ... の合計が 1 であるという事実から導き出されます。したがって、最悪の場合に行われる総仕事量は Θ(n) だけです。以前の Θ(n log n) の最悪のケースよりも優れています。
最後の詳細:なぜこれを行うのですか? 結局のところ、双方向リンク リストで要素を検索するには、すでに O(n) 時間かかります。このアプローチの主な利点の 1 つは、ランタイムが O(n) であっても、最終的に O(log n) 回の合計比較 (二分探索のステップごとに 1 回) しか実行できないことです。これは、比較にコストがかかる場合、O(n) は比較を行う作業ではなく、リストをたどって行われる作業に由来するため、通常の線形検索を行うよりも二分探索を使用する方が作業が少なくなる可能性があることを意味します。
于 2013-10-23T23:51:19.380 に答える