CountingSort Laufzeit

Neue Frage »

Auf diesen Beitrag antworten »
jordy CountingSort Laufzeit

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 ?
 
Auf diesen Beitrag antworten »
eulerscheZahl

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.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »