Welcher Algorithmus (Insertionsort bzw. Countsort) weist für große n im Worst Case eine bessere Laufzeit auf?

Question

Aufgabe:

Sei n die Eingabelänge eines Arrays und k die Größe des Wertebereichs. Es gelte, dass k=n³ ist. Somit wächst die Größe des Wertebereichs kubisch mit der Größe der Eingabe. Welcher der beiden Algorithmen (Insertionsort bzw. Countsort) weist für große n im Worst Case unter diesen Annahmen eine bessere Laufzeit auf?

Wie soll man diese Aufgabe zu Laufzeit lösen? Ich verstehe leider gerade nur Bahnhof, die Frage ist leider etwas kmisch formuliert, wie ich finde.

Was ich weiß ist, dass Insertionsort anfangs eine bessere Laufzeit aufweist als Countsort, bei größeren Werten ändert dies sich allerdings sehr schnell.

Insertionsort besitzt im Worst Case Θ(n^2) und Countsort O(n+k).
Wenn nun k = n^3 wäre dann Insertionsort dennoch größer?

Answer 1

Insertionsort bietet die Funktion Θ=(n²) nur als Annäherung an die Funktion der Laufzeit des Algorithmus. Es werden also weitere Summanden vernachlässigt.

Countingsort bietet mit O(n+k) eine super Laufzeit in Bezug auf die Menge von Werten, wobei die Zeit sich linear verlängert, je größer die Zahlen, die sortiert werden sollen werden. K ist also der Zahlenbereich, der zu sortieren ist. Da das Theta (Θ) sagt, dass der Funktionswert genauso schnell wächst, wie die Funktion in den Klammern. Das große O sagt, dass es nicht wesentlich langsamer wächst, also im Grunde fast das gleiche.

Wenn es um den Speicher geht, der verwendet wird, ist Insertionsort klar im Vorteil (O(1)). Countingsort hat O(k).

Von daher:

Wenn k=n³ wird, ist Insertionsort immernoch im Nachteil. Ich würde zwar keine der beiden Algorithmen wählen, aber Countingsort wäre zwischen den beiden immer(!) die beste Wahl.

Auch dir lege ich folgende Seite ans Herz:

bigocheatsheet.com

Beste Grüße

Felix