计数排序的时间复杂度

Question

11

我正在学习算法课程，发现计数排序的时间复杂度为O(n+k)，其中k是数字范围，n是输入大小。我的问题是，当k和n之间的差异太大时，比如k=O(n²)或O(n³)，我们能否说复杂度为O(n²)或O(n³)？在这种情况下，计数排序不是一个明智的选择，我们可以使用归并排序。我的理解正确吗？

- user2110714

2个回答

3

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

- Robert S. Barnes

你假设在基数为n的数字上进行O(1)操作。这似乎不太可能普遍成立。 - jfs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NPE · Accepted Answer

是的，您在所有方面都是正确的。

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