![[HaBo]](/styles/default/logoklein.png){kind=small}
Hallo!
Für's Studium beschäftige ich mich gerade mit der Frage, wie man denn die Laufzeit eines beliebigen Programms (bzw. Algorithmus) "herausfindet". Bei einfachen Laufzeiten wie O
oder O(n²) ist das ja meist recht einfach.
Schwieriger wird es hingegen schon bei Algorithmen, die etwas fortgeschrittener sind. Als Beispiel nehm ich einfach mal Mergesort. Wie kommt man denn darauf, dass Mergesort eine Laufzeit von O(n*log) hat? Gibt es da vielleicht ein paar einfache Tricks, die einem dabei helfen?
Für's Studium beschäftige ich mich gerade mit der Frage, wie man denn die Laufzeit eines beliebigen Programms (bzw. Algorithmus) "herausfindet". Bei einfachen Laufzeiten wie O
oder O(n²) ist das ja meist recht einfach.Schwieriger wird es hingegen schon bei Algorithmen, die etwas fortgeschrittener sind. Als Beispiel nehm ich einfach mal Mergesort. Wie kommt man denn darauf, dass Mergesort eine Laufzeit von O(n*log
) hat? Gibt es da vielleicht ein paar einfache Tricks, die einem dabei helfen?
