CountingSort Laufzeit |
12.01.2016, 11:44 | 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 ? |
|
|
12.01.2016, 16:52 | 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. |
|