0
int[] countingSort(int[] a, int k) {
int c[] = new int[k];
for (int i = 0; i < a.length; i++) //{1}
c[a[i]]++;
for (int i = 1; i < k; i++) //{2}
c[i] += c[i-1];
int b[] = new int[a.length];
for (int i = a.length-1; i >= 0; i--) //{3}
b[--c[a[i]]] = a[i];
return b;
}
它指出下面的代碼片段，所述運行時間爲O（n + k）的時間.K是輸入 數組a的範圍內。
任何人都可以解釋爲什麼運行時間是O（n + k）。 ？
如果我們看代碼片段，看到{1} for循環運行n次，{2}運行在K時間，第三次運行也n次所以總運行時間應該是O（2n + k）時間。我的計算不正確？常數2在這裏被忽略了嗎？