对计数排序算法的复杂性感到困惑

Question

我对计数排序算法有两个疑惑：

复杂度怎么只有O(n)？算法中有 5 个 for 循环。每个for循环的复杂度应该是n吗？所以导致 n^4 复杂？我知道我错了，计数排序是线性的，但我想知道为什么我的推理是错误的。
如果计数排序算法是线性的，为什么是O(n+K)而不仅仅是O(n)，如果加上K就不再是线性的了对吧?

这也是我指的计数排序代码：

void countSort(char *str)
{
    // The output character array that will have sorted str
    char output[strlen(str)];

    // Create a count array to store count of inidividul characters and
    // initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    // Store count of each character
    for(i = 0; str[i]; ++i)
        ++count[str[i]];

    // Change count[i] so that count[i] now contains actual position of
    // this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];

    // Build the output character array
    for (i = 0; str[i]; ++i)
    {
        output[count[str[i]]-1] = str[i];
        --count[str[i]];
    }

    // Copy the output array to str, so that str now
    // contains sorted characters
    for (i = 0; str[i]; ++i)
        str[i] = output[i];
}

Answer 1

回答1：

设三个 'for' 循环，每个循环在 O(n) 中工作因此整体复杂度为：

O(n)+O(n)+O(n) = O(n+n+n) = O(3n)

在3n的情况下，3是一个常量，可以忽略，因此复杂度降低为O(n)

回答2：

算法不仅取决于数组的大小N，还取决于其中收集的数字的范围K。它需要一个更大的计数数组，因此需要迭代来对数组进行计数排序：

{1,10000000,3,2,0} // K=10000001

比它会：

{1,4,5,2,3} // K=6

因此使用您的代码的 for 循环的复杂度是这样计算的：

for(i = 0; str[i]; ++i) // O(n)

for (i = 1; i <= RANGE; ++i) // O(k)

for (i = 0; str[i]; ++i) // O(n)

for (i = 0; str[i]; ++i) // O(n)

总体复杂度是 O(n)+O(n)+O(n)+O(k) = O(n+k) 并指出我对你问题的回答：算法复杂度仍然被视为线性的。

Answer 2

渐近复杂度在某种意义上显示了作为输入大小函数的操作数。这很有用，因为它显示了算法随着输入大小的增长而减慢了多少。常量不会影响减速，因此会被忽略。忽略我们得到的常量：

strlen(str) 执行 strlen(str) 次操作（它检查整个字符串直到找到 '[=12=]'）
memset() 执行 strlen(str) 次操作
第二个 for 执行 RANGE 次操作
其他三个 for 中的每一个都执行 strlen(str) 次操作

在您的示例中，strlen(str) 表示为 n，RANGE 表示为 K。所以整个函数执行 O(5n + K) = O(n + K) 操作。

n + K 仍然是一个线性函数，它是两个变量（它是幂 1 的多项式）。

要对此有更深入的了解，您需要阅读更多有关渐近复杂性（严格的数学理论）的内容。

对计数排序算法的复杂性感到困惑

Confused about complexity of counting sort algorithm

c

counting-sort