计数排序运行次

Question

下面的代码片段来自这个 link

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;
}

表示运行ning时间为O(n+k)时间.k为输入范围数组 a .

谁能解释一下为什么运行ning 时间是 O(n+k)。？

如果我们查看代码片段并看到 {1} for 循环运行s 在 n 时间，{2} 运行s 在 K 时间和第三个运行s 也在 n 时间所以总运行时间应该是 O(2n+k) 时间。我的计算不正确吗？这里忽略常量2了吗？

Answer 1

你的计算也是正确的，因为O(2n+k) = O(n+k).

对于时间复杂度，只有多项式的次数是重要的，而不是系数。

所以； O(n) = O(2n) = O(3n) .... = O(xn)

请阅读https://en.wikipedia.org/wiki/Time_complexity#Linear_time

计数排序运行次

Counting sort running time

sorting

counting