Laufzeit von Quicksort/Mergesort --> nlogn

[Math55]

hi, kann mir jemand erklären, warum diese algorithmen eine laufzeit von nlogn haben? ich kapier nicht, wie das log da rein kommt :-|....die stehen zwar überall schön erklärt, aber wie die laufzeit zustande kommt, steht nirgends.

vielen dank!!

gruß

 

[mic_checker]

Also wenn ich mich recht erinnere hat Quicksort keine Laufzeit von n log n zumindest keine gesicherte Laufzeit von n log n.

 

[Bleiglanz]

wegen der halbiererei

kennst du das spiel wo man eine zahl zwischen eins und 1024 erraten muss und so anfängt

Ist sie grösser 512?
....

wie oft kannst du das wohl machen? ursprünglich steht ja immer der log_2 da, aber weils nur um die grössenordnung geht, schreibt man einfach logn

 

[Math55]

erklär mal genauer, bitte. wieso gerade log. was drückt das aus?

danke

 

[mic_checker]

Bleiglanz hat doch ein typisches Beispiel gebracht: Du musst ne Zahl in nem best. Bereich erraten.

Dazu halbierst du immer die einzelnen Teilbereiche bis du schließlich die Zahl hast. Sagen wir du hast 8 Elemente, dann brauchst du 3 Versuche um das Element zu raten, wie du siehst 2³ = 8.
Das ist natürlich ein Vorteil gegenüber linearer Laufzeit, wo du naiv einfach nur raten würdest: Ist es 1, 2 , 3 , 4 etc. - du kannst zwar Glück haben und direkt richtig raten, im Worst Case aber errätst du es erst am Ende, somit hättest du ne Komplexitätsklasse von O(n).

Schau dir dazu auch mal z.B. die Binäre Suche an, um das prinzipielle Konzept der "Halbierungen" etc. zu verstehen.

 

[Bleiglanz]

Weisst du überhaupt was "log" ist?



n/2 Schritt 1

n/4 Schritt 2

n/8 Schritt 3
...

irgendwann zu ende, d.h. nur noch 1, sagen wir bei n/(2^k)

dann ist aber k = die Anzahl der Schritte

ungefähr das gleiche wie der log zur Basis 2, denk mal drüber nach oder den über

java.util.Arrays.binarySearch

nach