| Die letzten 2 Beiträge |
| 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. |
| 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 ? |
|
|
