Komplexität Logarithmus

liselotte
Neuling
Neuling
Beiträge: 10
Registriert: 14. Mai 2017 16:09

Komplexität Logarithmus

Beitrag von liselotte » 18. Sep 2017 10:53

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

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Komplexität Logarithmus

Beitrag von Hans123 » 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.

liselotte
Neuling
Neuling
Beiträge: 10
Registriert: 14. Mai 2017 16:09

Re: Komplexität Logarithmus

Beitrag von liselotte » 19. Sep 2017 15:27

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!

Antworten

Zurück zu „Archiv“