Exakte durchschnittliche Komplexität der binären Suche

Question

Ich habe mich in letzter Zeit intensiv mit der Binären Suche beschäftigt. Dabei sind mir einige Muster aufgefallen, die recht interessant sind, und als ich dann im Internet nachgeschaut habe, wurde die durchschnittliche Komplexität nur grob dem Typ O(log n) zugeteilt.

Nun meine Frage: ist bereits eine( explizite) Formel bekannt, um dies zu berechnen?

Die Muster:

Die durchschnittliche Komplexität  ist bei Anzahl A der Objekte ,A E N, A >3 , ja (Summe der Länge aller Pfade( hier nenn ich es mal m))/ A.

Für  2^(n-1)<= A < 2^(n-1) *1.5 ist 

m(A) = m(A-1) + n

Für 2^(n-1) *1.5<= A < 2^n ist

m(A) = m(A-1) +n-1

Außerdem gibt es noch einige weitere Muster, aber das würde hier zu lang werden, deshalb könnte ich auf Anfrage eine Excel Tabelle anbieten. 

Vielen Dank schon mal für die Antworten 

P.S. Entschuldigung für die kursive Schrift und den fehlenden hochgestellten Text, aber die Knöpfe buggen in der mobilen Version etwas. 

Comments

Hallo Ezylryb, frag das am besten mal in der Community "Informatik".

Answer 1

Die durchschnittliche Komplexität

Wenn man Aussagen über die durchschnittliche Komplexität treffen möchte, dann muss man im Allgemeinen eine Wahrscheinlichkeitsverteilung für die Eingaben angeben.

Im Extemfall ist ein binärer Suchbaum eine Liste und hat demnach lineare Komplexität bei der Suche.

Der andere Extremfall ist ein vollständig balancierter Baum. Der wird aber selten erreicht, weil das Einfügen zu aufwändig ist. Meistens begnügt man sich mit einer Zwischenlösung, wie zum Beispiel AVL-Bäumen oder RB-Bäumen.

wurde die durchschnittliche Komplexität nur grob dem Typ O(log n) zugeteilt.

Das hat mathematisch eine präzise Bedeutung. Wenn du über die mathematische Definition von O(log n) hinaus Aussagen machen möchtest, dann musst du angeben, welches Rechnermodell zugrunde liegt. Binäre Suche ist nur dann O(log n), wenn Vergleiche und die Navigation von einem zum nächsten Knoten O(1) sind.

die Knöpfe buggen in der mobilen Version etwas.

Die Geißel unserer Zeit. Aber früher war es auch nicht besser.

(Summe der Länge aller Pfade( hier nenn ich es mal m))/ A.

Ein zu einer linearen Liste entarteter Suchbaum hat einen Pfad der Länge A-1. Laut deiner Aussage wäre die durchschnittliche Komplexität dann (A-1)/A. Das ist kleiner als 1.