Seite 1 von 1

Komplexität Logarithmus

Verfasst: 18. Sep 2017 10:53
von liselotte
Hallo,
in der Vorlesung kam ein Beweis. Es ging darum, dass die maximale Anzahl von Vergleichen bei Mergesort in Ω(n lgn) liegt. Wie kommt man auf den Logarithmus?
Liebe Grüße und vielen Dank

Re: Komplexität Logarithmus

Verfasst: 19. Sep 2017 10:44
von Hans123
In Mergesort teilst du ja deine Sequenz von Länge n solange in zwei Teile, bis alle Sequenzen Länge eins haben. Das bedeutet, du musst immer mindestens (mindestens deshalb, weil du aufrunden musst) log(n) mal teilen. Beispiel: log(8) -> 3, weil 8->4->2->1, drei mal teilen.
Die Umkehrfunktion von log zur Basis zwei ist 2^x, mit x=3 hättest du dann wieder acht.

Re: Komplexität Logarithmus

Verfasst: 19. Sep 2017 15:27
von liselotte
Hans123 hat geschrieben:
19. Sep 2017 10:44
In Mergesort teilst du ja deine Sequenz von Länge n solange in zwei Teile, bis alle Sequenzen Länge eins haben. Das bedeutet, du musst immer mindestens (mindestens deshalb, weil du aufrunden musst) log(n) mal teilen. Beispiel: log(8) -> 3, weil 8->4->2->1, drei mal teilen.
Die Umkehrfunktion von log zur Basis zwei ist 2^x, mit x=3 hättest du dann wieder acht.
Ist klar geworden. Vielen Dank!