Ein allgemeiner Vergleich

Was ist jetzt besser?

Wir haben schon einige Unterschiede zwischen binaereSuche, naiveSuche und deinem Algorithmus gesehen. Du weißt vielleicht schon, welcher Algorithmus wann anzuwenden ist. Wir wollen es uns hier trotzdem nochmal in der Verallgemeinerung gemeinsam anschauen.

Eine Verallgemeinerung

Eine verallgemeinerte Darstellung unseres Problems können wir sehr einfach formulieren: Wir wollen möglichst effizient in einem Datensatz bestehend aus n Elementen, m mal ein Element heraussuchen.

Dir ist vielleicht aufgefallen, dass es eine erhebliche Rolle spielt, welches Element Du in einer Liste suchst. Der Einfachheit halber beschäftigen wir uns hier mit dem worst-case, gehen also davon aus, dass wir immer das Element der Datenmenge suchen, welches am meisten Vergleiche benötigt.

Laufzeit des naiven Algorithmus

Wir wollen uns zuerst den naiven Algorithmus anschauen. Wir haben eine Liste mit n Argumenten und vergleichen eine Zahl mit jedem einzelnen Listenelement, bis wir es finden.

Wir können also nach nur einem Vergleich fertig sein, wenn die Zahl an der ersten Stelle in der Liste steht, nach zwei Vergleichen, wenn die Zahl an der zweiten Stelle steht, und so weiter, bis hoch zu n Vergleichen, wenn die Zahl an der n-ten Stelle steht. Da wir uns wie gesagt erstmal nur mit dem worst-case beschäftigen wollen, brauchen wir also n Vergleiche.

Wenn wir jetzt noch die Anzahl unserer Suchen berücksichtigen, können wir diese Laufzeit jetzt einfach mit der Anzahl unserer Suchen multiplizieren, kommen also auf:n*m

Laufzeit des binären Algorithmus

Beim binären Algorithmus müssen wir zunächst unsere Liste sortieren. Natürlich müssen wir das nicht jedesmal machen, wenn wir ein Element suchen. Wenn sie einmal sortiert ist, können wir immer wieder in der sortierten Liste suchen.

Wer sich mit den Laufzeiten von quicksort nicht auskennt, kann sich darüber hier informieren. Alternativ kann er auch einfach glauben, dass quicksort eine Liste mit n Elementen im worst-case mit n² Vergleichen sortiert.

Danach kann das Element natürlich auch hier das erste Element sein, welches wir finden, welches hier im Median liegt. Es kann auch das zweite Element sein, welches wir finden. Allerdings gibt es im zweiten Schritt bereits zwei Elemente, die möglich sind (das im Median der linken Teilliste und das im Median der rechten Teilliste).

Da wir aber natürlich auch hier den worst-case betrachten, können wir davon ausgehen, dass unser Element erst beim letzten Vergleich gefunden wird. Der wie vielte Vergleich ist das aber?

Im ersten Schritt brauchen wir maximal zwei Vergleiche (um = und < zu prüfen), danach haben wir allerdings nur noch rekursiv die Hälfte der Liste zu durchsuchen. Da wir rekursiv durchsuchen brauchen wir wie im ersten Fall immer maximal zwei Vergleiche und halbieren die Elemente weiter, bis es nur noch eins gibt. Spätestens dann finden wir das Element (so es denn in unserer Liste ist).

Da wir die zu durchsuchende Menge mit jedem Schritt halbieren kommen wir also auf ld(n)*2 (aufgerundet) Vergleiche, wobei ld der logarithmus dualis, also der logarithmus zur Basis 2 ist. Insgesamt damit also n²+ld(n)*m Vergleiche.

Vergleiche

Wir sehen, dass unsere binäre Suche besser wird, je häufiger wir suchen müssen, also je größer m wird. Insbesondere ist unsere binäre Suche überlegen, wenn m deutlich größer als n ist.

Erinnern wir uns noch einmal an unser Beispiel: Die Hans-Wurst Schule mit 80 Schülern, von denen jeder 20 Mal im Jahr gesucht wird. Wir haben hier also n=80 Schüler und m=1600 Suchanfragen.

In unserem Beispiel haben wir also in der Tat eine Laufzeit von 80*1600=128000 Vergleichen für unseren naiven Algorithmus zu 80²+ld(80)*2*1600=26630 Vergleichen für unseren binären Algorithmus haben, unser naiver Algorithmus ist hier also etwa fünf mal langsamer.

Average Case

Jetzt könnte man natürlich behaupten, dass es ähnlich wie bei quicksort und mergesort ist und die naive Suche dennoch besser ist, da der worst case praktisch nicht auftritt (auch wenn es bei quicksort und mergesort eher andere Argumente sind, die für quicksort sprechen).

Jedoch ist das einzige, was sich bei der naiven Suche im average case ändert der Einfluss des Faktors n. Überlegen wir uns also, wie dieser im Durchschnitt ist.

Da wir nichts über unsere Verteilung wissen, ist die Wahrscheinlichkeit für jede Position der Liste unser Element zu enthalten gleich, bei n Elementen also 1/n. Ist unser gesuchtes Element an Position 1, brauchen wir einen Vergleich, an Position 2 zwei Vergleiche, usw. bis schließlich an Position n n Vergleiche nötig sind. Unser nun gesuchter durchschnittliche komplexer Fall lässt sich jetzt also einfach über die Wahrscheinlichkeitsverteilung berechnen:

1/n*1 + 1/n*2 + ... + 1/n*(n-1) * 1/n*n = n/2

Um also nochmal zu unserem Beispiel zu kommen haben wir nun im average-case eine Anzahl von (80/2)*1600=56000 Vergleichen, also 2,5 mal so viele Vergleiche wie der worst-case bei binaereSuche. Diese Differenz wird natürlich wieder noch extremer, wenn wir auch dort den average-case betrachten, was wir uns hier allerdings jetzt sparen wollen.

Ist binaereSuche immer besser?

Wir haben gesehen, dass binaereSuche schneller ist, weil es ein Element schneller findet, dafür aber vorher die Liste sortieren muss. Da es das nur einmal tun muss, ist binaereSuche besser, wenn wir viele Suchen durchführen müssen. Wenn wir die Laufzeiten für nur eine Suche vergleichen, gewinnt natürlich naiveSuche mit n Vergleichen gegen n² ld(n) Vergleichen.