DSA 计数排序时间复杂度

请查看 此页面 了解时间复杂度的概述。

计数排序时间复杂度

计数排序 的工作原理是首先统计不同值的出现次数，然后利用这些信息以排序后的顺序重新创建数组。

作为经验法则，当可能的取值范围 \(k\) 小于值的个数 \(n\) 时，计数排序算法运行速度很快。

为了用大 O 符号表示时间复杂度，我们需要首先计算算法执行的操作次数。

• 寻找最大值：每个值都需要评估一次以确定它是否为最大值，因此需要 \(n\) 次操作。
• 初始化计数数组：数组中的最大值为 \(k\)，我们需要在计数数组中包含 \(k+1\) 个元素才能包含 0。计数数组中的每个元素都需要初始化，因此需要 \(k+1\) 次操作。
• 我们要排序的每个值都计数一次，然后删除，因此每次计数进行 2 次操作，总共 \(2 \cdot n\) 次操作。
• 构建排序后的数组：在排序后的数组中创建 \(n\) 个元素：\(n\) 次操作。

总共得到

\[ \begin{equation} \begin{aligned} 操作 {} & = n + (k+1) + (2 \cdot n) + n \\ & = 4 \cdot n + k + 1 \\ & \approx 4 \cdot n + k \end{aligned} \end{equation} \]

根据我们之前了解的时间复杂度，我们可以使用大 O 符号创建一个简化的表达式来表示时间复杂度

\[ \begin{equation} \begin{aligned} O(4 \cdot n + k) {} & = O(4 \cdot n) + O(k) \\ & = O(n) + O(k) \\ & = \underline{\underline{O(n+k)}} \end{aligned} \end{equation} \]

前面已经提到，当不同值的范围 \(k\) 相对于要排序的总值个数 \(n\) 相对较小时，计数排序非常有效。现在我们可以直接从大 O 表达式 \(O(n+k)\) 中看到这一点。

例如，假设不同数字的范围 \(k\) 是要排序的值个数的 10 倍。在这种情况下，我们可以看到该算法将大部分时间花在处理不同数字的范围 \(k\) 上，尽管要排序的实际值个数 \(n\) 相对较小。

由于时间复杂度受值范围 \(k\) 的影响很大，因此无法像以前那样直接用图表来表示计数排序的时间复杂度，也无法模拟时间复杂度。

下面是一个图，它显示了计数排序的时间复杂度可能会有多大变化，后面是最佳和最坏情况的解释。

计数排序的最佳情况是范围 \(k\) 只是 \(n\) 的一小部分，比如 \(k(n)=0.1 \cdot n\)。例如，对于 100 个值，范围将为 0 到 10，或者对于 1000 个值，范围将为 0 到 100。在这种情况下，时间复杂度为 \(O(n+k)=O(n+0.1 \cdot n) = O(1.1 \cdot n)\)，简化为 \(O(n)\)。

然而，最坏情况是如果范围远大于输入。例如，对于只有 10 个值的输入，范围在 0 到 100 之间，或者类似地，对于 1000 个值的输入，范围在 0 到 1000000 之间。在这种情况下，\(k\) 的增长相对于 \(n\) 是二次的，像这样：\(k(n)=n^2\)，我们得到时间复杂度 \(O(n+k)=O(n+n^2)\)，简化为 \(O(n^2)\)。还可以构建比这更糟糕的情况，但选择这种情况是因为它相对容易理解，而且可能并不完全不现实。

正如您所见，在选择计数排序作为您的算法之前，务必考虑值的范围与要排序的值个数的比较。此外，如页面顶部所述，请记住，计数排序仅适用于非负整数。

计数排序模拟

运行计数排序的不同模拟，以查看操作次数如何介于最坏情况 \(O(n^2)\)（红线）和最佳情况 \(O(n)\)（绿线）之间。

如前所述：如果要排序的数字在值上变化很大（\(k\) 很大），而要排序的数字很少（\(n\) 很小），则计数排序算法效率不高。

如果我们保持 \(n\) 和 \(k\) 固定，则模拟中上述“随机”、“降序”和“升序”选项会导致相同的操作次数。这是因为在这三种情况下都发生了相同的事情：设置一个计数数组，对数字进行计数，然后创建新的排序数组。