バイナリ検索の最適性

Question

これはばかげた質問かもしれませんが、バイナリ検索が漸近的に最適であるという証拠を誰かが知っていますか？つまり、それらのオブジェクトの唯一の許可された操作が比較である要素のソートされたリストが与えられた場合、検索がO（LG N）で実行できないことをどのように証明しますか？ （ちなみに、それはLg nの小さなOです。）これは、唯一の操作が許可された操作が比較である要素に制限していることに注意してください。データに対してより複雑な操作を行うことが許可されている場合（たとえば、補間検索を参照）。

Answer 1

から ここ:

• 考えられる結果の数は、少なくともo（n）でなければなりません。
• 「決定ツリー」のノードによってアルゴリズムによって行われる決定を表すことができます。アイテムが途中で進むよりも大きい場合、それが逆になると比較されます。ツリーのノードはアルゴリズムの状態であり、葉は結果です。したがって、ツリーには少なくともo（n）ノードがあるはずです。
• O（n）ノードの各ツリーには、少なくともO（log n）レベルがあります。

Answer 2

ロジックは簡単です。の配列があると仮定しましょう n 異なるソートされた要素。

1. 1つの比較の結果が2つあります（最初の要素は小さいか大きいです）。したがって、1つの比較で十分な場合、 n <= 2. 。それ以外の場合、3つの要素がある場合（a, b, c）そして、私たちのアルゴリズムには2つの可能な結果があり、3つの要素のうちの1つは選択されません。
2. 2つの比較の結果が4つあります。したがって、2つの比較で十分な場合、 n <= 4.
3. 同様に、 k 比較で十分です n あるべきです n <= 2^k.

最後の不平等を逆にすると、対数があります。 k >= log(2, n).

Answer 3

ニキータが説明したように、何かを持っていることは不可能です いつも O（log n）よりも優れています。

追加の操作を許可したとしても、それでもまだ十分ではありません - 補間検索がバイナリ検索よりも悪いパフォーマンスを発揮する要素シーケンスを準備することが可能だと確信しています。

補間検索はより良いと言えます。

1. 最悪の場合ではなく、平均パフォーマンスを検討します。
2. 可能な各受信データセットの確率は不均一です。

そのため、答えは - それはすべて、着信データセットに関する追加の知識に依存します。