Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » CountingSort Laufzeit

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

CountingSort Laufzeit

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

jordy
unregistriert

CountingSort Laufzeit

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Algorithmus :
For i <- 0 to k do C[r] <- 0
For i <- 1 to n C[A[i]] <- C[A[i-1]] + C[A[i]]
For r <- 1 to k do C[r ] C[r 1048576- 1] + C[r ]
For i <- n downto 1 do B[C[A[i ]]] <- A[i ],
C[A[i ]] C[A[i ]] - 1048576 1.

Die Laufzeit ist Theta(n+k). Warum ?

Meine Ideen:
Ich zähle zur Laufzeitbestimmung doch die Anazhl der ausgeführten For-Schleifen .
Für Theta(n+k) würde man doch aber nur die zweite und dritte Schleife berücksichtigen ?

12.01.2016 11:44

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Du hast 4 Schleifen, 2 mit Laufzeit Theta(n) und 2 mit Theta(k).
Die Gesamtlaufzeit wird durch die größte Einzelzeit bestimmt. Da du aber nicht weißt, ob n oder k größer ist, eben Theta(n+k). Es würde auch Theta(max(n, k)) gehen.

__________________
Syntax Highlighting fürs Board (Link)

12.01.2016 16:52

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » CountingSort Laufzeit