0 Daumen
701 Aufrufe

Hallo, vielleicht kann mir jemand dabei helfen :)

Frage:

Betrachten Sie eine unsortierte Liste mit 1.000.000 Elementen. In dieser sollen Sie 30 Mal nach jeweils einem Element suchen. Welche Strategie ist schneller?


-Verwendung der linearen Suche
-Vorsortierung durch Merge-Sort (Laufzeit O(n log(n)) und danach Verwendung der binären Suche.


Hinweis:
Für die Laufzeit nehmen Sie der Einfachheit halber an, dass beispielsweise für einen Algorithmus aus O(n) eine Laufzeit von n gilt; nehmen Sie bei Logarithmen weiterhin den Logarithmus zur Basis 2 an.

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

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

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community