DSA 基数排序时间复杂度

请参阅 此页面 以了解时间复杂度的通用解释。

基数排序时间复杂度

该 基数排序 算法一次对非负整数排序一位。

有 \(n\) 个需要排序的值，\(k\) 是最高值中的位数。

基数排序运行时，每个值都会被移动到基数数组中，然后每个值都会被移回初始数组。因此，有 \(n\) 个值被移动到基数数组中，\(n\) 个值被移回。这给了我们 \(n + n=2 \cdot n\) 个操作。

并且上述描述的移动值需要对每一位进行。这给了我们总共 \(2 \cdot n \cdot k\) 个操作。

这给了我们基数排序的时间复杂度

\[ O(2 \cdot n \cdot k) = \underline{\underline{O(n \cdot k)}} \]

基数排序可能是最快的排序算法，只要位数 \(k\) 相对于值数 \(n\) 保持相对较小。

我们可以想象一种场景，其中位数 \(k\) 与值数 \(n\) 相同，在这种情况下，我们得到时间复杂度 \(O(n \cdot k)=O(n^2)\) ，这相当慢，并且具有与例如冒泡排序相同的时间复杂度。

我们还可以想象一种场景，其中位数 \(k\) 随着值数 \(n\) 的增长而增长，因此 \(k(n)= \log n\)。在这种情况下，我们得到时间复杂度 \(O(n \cdot k)=O(n \cdot \log n )\)，这与例如快速排序相同。

请参见下图中基数排序的时间复杂度。

基数排序模拟

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

表示不同值的条形图已按比例缩放以适合窗口，使其看起来不错。这意味着 7 位数的值看起来仅仅比 2 位数的值大 5 倍，但实际上，7 位数的值实际上比 2 位数的值大 5000 倍！

如果我们保持 \(n\) 和 \(k\) 固定，上述模拟中的“随机”、“降序”和“升序”选项会导致相同数量的操作。这是因为这三种情况下的操作都是一样的。