Laufzeit Mergesort
-
Hallo,
wie kann man denn begründen, das Mergesort eine Laufzeit von O(n*log n) hat?
-
Indem man Wikipedia liest.
-
Ist halt'n Divide&Conquer-Algorithmus. Daraus kannst Du schonmal auf das log(n) schließen. Dann überlegst Du Dir, wie groß der Aufwand ist, um das Problem in zwei kleinere zu unterteilen bzw. nachher wieder zusammenzusetzen. Da kommt dann das N her.
