最近、リンクされたリストに関する 1 つの興味深い質問に出くわしました。ソートされた単一リンクリストが与えられ、このリストから 1 つの要素を検索する必要があります。
時間計算量は を超えてはなりませんO(log n)。これは、この連結リストに二分探索を適用する必要があるようです。どのように？リンクされたリストはランダムアクセスを提供しないため、二分探索アルゴリズムを適用しようとすると、リストの長さを見つけて中央に移動する必要があるため、O(n) に到達します。
何か案は？
57108 次
6 に答える
43
単純な単一リンクリストでは確かに不可能です。
スケッチ証明：単一リンクリストの最後のノードを調べるにはn-1、「次の」ポインターをたどる操作を実行する必要があります[ k+1thノードへの参照が1つだけであり、それがthkにあるという事実の帰納法による証明ノード、およびそれに従うための操作が必要です]。特定の入力については、最後のノードを調べる必要があります（具体的には、検索対象の要素がその値以上であるかどうか）。したがって、特定の入力の場合、必要な時間はに比例しnます。
より多くの時間が必要か、別のデータ構造が必要です。
バイナリ検索を使用したO（log n）比較で実行できることに注意してください。それよりも時間がかかるため、この事実は、比較がリストトラバーサルよりもはるかに高価である場合にのみ重要です。
于 2011-03-12T09:45:45.357 に答える
32
スキップ リストを使用する必要があります。これは、通常のリンクされたリストでは不可能です (そして、これが通常のリストで可能かどうかを知りたいです)。
于 2011-03-12T06:48:23.340 に答える