Zeigen Sie, dass die Anzahl der Vergleiche dieser Methode im Mittel aus O(n) ist

Question

Frage:

Bei die Methode Suchen in Listen, bei der die Folge F mithilfe eines Pivotelements in zwei Teilfolgen
F1 und F2 aufgeteilt wird. F1 enthält die Elemente mit Schlüsseln, die kleiner als das
Pivotelement sind, und F2 die Elemente mit Schlüsseln, die gröÿer als das Pivotelement
sind. Anschlieÿend wird in der passenden Teilfolge rekursiv weiter gesucht.

Zeigen Sie, dass die Anzahl der Vergleiche dieser Methode im Mittel aus O(n) ist

könnte jemand mir bitte helfen?

Answer 1

Hi!

Die Laufzeit der binären Suche beträgt O(log₂ n) und nicht nicht O(n).

Logisch, denn du halbierst ja mit jedem Schritt die Liste.

Bei der binären Suche liegt bereits eine sortierte Folge vor. Durch die Wahl des Pivotelements als mittleres Element fallen immer mind. n/2 -1 Elemente weg, weswegen wir niemals auf n Vergleiche im Worst case oder gar im average case kommen.

Beste Grüße

Felix