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在这里被忽略了吗？