Unterschied zwischen linearem Wachstum und "super linearem Wachstum"?
Wir haben in Informatik momentan als Thema Sortierverfahren und jeder im Kurs soll eines vorstellen. Nun, ich habe den Quicksort zugeteilt bekommen und ich soll mich bei diesem ebenfalls mit der Laufzeit auseinandersetzen. Beim Quicksort beträgt die Laufzeit im worst-case O(n^2), was ich ja noch verstehe. Im average und im best-case beträgt diese aber O(n*log(n)) und ich weiß bei Leibe nicht was das heißen soll.
Ich hatte daraufhin mal auf Wikipedia nachgeschaut, aber da stand nur das es sich um ein super lineares Wachstum handelt und ich habe leider keine Ahnung, was das heißen soll...
Wäre nett, wenn das irgendwer zufällig wissen sollte. :)
2 Antworten
O(n^2) bedeutet (zumindest lese ich das so), dass mit steigendem n der Aufwand mit dem Quadrat der Anzahl der zu sortierenden Objekte - also "n" - wächst; es ist progressiv
Beispiele:
- n=1 → n²=1
- n=2 → n²=4
- n=3 → n³=9
- n=100 → n²=10000
- .... usw.
Bei O(n*log(n) ist das Wachstum degressiv, es wird also immer langsamer.
Beispiele:
- n=1 → n·log(n) = 1
- n=2 → ... = 0,6
- n=3 → ... = 1,43
- n=100 → ...= 200
Den Ausdruck "superlineares Wachstum" kenne ich allerdings auch nicht.
Noch nie etwas von "super lineaem Wachstum" gehört. Die O Notation beschreibt die performance eines Algorithmus in Relation zur Größe der Eingabe.
Ich hab davon auch noch nie was gehört...deshalb bin ich ein bisschen unsicher