Hi!
Zwei simple Rechnungen:
Für die lineare Suche von 30 Elementen ergibt sich folgendes:
O(1000000 * 30) = O(30.000.000)
Für die binäre Suche ergibt sich:
O(30* log(1000000)) als Laufzeit für die Suche, plus
O(1000000 * log(1000000)) für die Laufzeit der Sortierung mit Mergesort.
Das sind zusammen:
O(19 931 569) + O(598) = O(19 932 166)
Daraus folgt:
Die Sortierung mit Mergesort und anschließender binären Suche wird, je mehr Elemente gesucht werden müssen, deutlich schneller, als die lineare Suche ohne Sortieren.
Jetzt ließe sich noch mit etwas Mathematik und Gleichung unformen ausrechnen, für welches k (Anzahl der Suchen) die binäre schneller wird, als die lineare Suche.
k = (log(n)+n*log(n))/n
Für n dann 1 000 000 einsetzen.
k ≈ 19,9
Somit lohnt sich die binäre Suche mit Sortieren bei einer Anzahl von 1000000 Elementen ab 20 Wiederholungen.
Beste Grüße
Felix
