algorithm - 计数排序的时间复杂度

Question

我正在学习算法课程，在那里我看到计数排序的时间复杂度为 O(n+k)，其中 k 是数字范围，n 是输入大小。我的问题是，当k和n的差值太大时，比如k=O(n ² )或者O(n ³ )，我们可以说复杂度是O(n ² )还是O(n ³ ) ? 那么在这种情况下计数排序不是一个明智的方法，我们可以使用归并排序。我对吗？

Answer 1

是的，你在所有方面都完全正确。

此外，我们可以做出更强有力的陈述：当 k=O(n ² ) 或 O(n ³ ) 时，我们可以说计数排序的复杂度为 Θ(n ² ) 或 Θ(n ³ )。

Answer 2

理论上，您仍然可以在 O(n) 时间内进行排序。如果值的范围是 1 到 n ³，则转换为基数 n 并进行基数排序。在基数 n 中，数字有 3 位数字，因此基本转换的运行时间为 O(3n + 3n) + O(n)。总体 O(n)。