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.