0 Daumen
1,9k Aufrufe

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?

Avatar von

1 Antwort

0 Daumen

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

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community