Optimalität der binären Suche

Question

Dies mag eine dumme Frage sein, aber weiß jemand einen Beweis dafür, dass binäre Suche asymptotisch optimal ist? Wenn wir eine sortierte Liste von Elementen erhalten, bei denen die einzige zulässige Operation dieser Objekte ein Vergleich ist, wie beweisen Sie, dass die Suche in O (LG n) nicht durchgeführt werden kann? (Das ist übrigens wenig LG N.) Beachten Wenn Sie komplexere Operationen für die Daten ausführen dürfen (siehe beispielsweise Interpolationssuche).

Answer 1

Aus hier:

• Die Anzahl der möglichen Ergebnisse sollte mindestens O (n) sein.
• Sie können die vom Algorithmus getroffenen Entscheidungen durch Knoten eines "Entscheidungsbaums" darstellen: Wenn die Elemente mehr vergleichen, geht es weiter, wenn nicht in die andere Richtung geht. Die Knoten des Baumes sind die Zustände des Algorithmus und die Blätter sind die Ergebnisse. Es sollte also mindestens O (n) Knoten im Baum geben.
• Jeder Baum auf o (n) Knoten hat mindestens O (log n) -Spegel.

Answer 2

Die Logik ist einfach. Nehmen wir an, wir haben eine Reihe von n verschiedene sortierte Elemente.

1. Es gibt 2 mögliche Ergebnisse von 1 Vergleich (das erste Element ist kleiner oder höher). Wenn also ein Vergleich ausreicht, n <= 2. Sonst, wenn wir 3 Elemente haben (a, b, c) und unser Algorithmus hat 2 mögliche Ergebnisse, eines von 3 Elementen wird niemals ausgewählt.
2. Es gibt 4 mögliche Ergebnisse von 2 Vergleiche. Wenn also 2 Vergleiche genug sind, n <= 4.
3. Ebenso für k Vergleiche genug zu sein n sollte sein n <= 2^k.

Umkehren Sie die letzte Ungleichheit und Sie werden einen Logarithmus haben: k >= log(2, n).

Answer 3

Wie Nikita beschrieb, ist es unmöglich, etwas zu haben stets Besser als O (log n).

Selbst wenn Sie einige zusätzliche Operationen ausführen dürfen, ist es immer noch nicht genug - ich bin sicher, dass es möglich ist, Elemente -Sequenz vorzubereiten, bei denen die Interpolationssuche schlechter abschneidet als die binäre Suche.

Wir können sagen, dass die Interpolationssuche nur besser ist, weil:

1. Wir betrachten die durchschnittliche Leistung, nicht den schlimmsten Fall.
2. Die Wahrscheinlichkeit jedes möglichen eingehenden Datensatzes ist ungleichmäßig.

Die Antwort lautet also - alles hängt von dem zusätzlichen Wissen ab, den wir über eingehende Datensätze haben.