arrays - 具有已知上限的桶排序的复杂性？

Question

假设我们有一个数组，我们知道所有元素都是 0...2n 并且没有排序。

如果我们使用复杂度为 O(n+k) 的桶排序算法，其中 k 是元素的范围，在本例中为 2n，那么对这个数组进行排序的复杂度是否会是 Θ(n)？

我的基本原理是运行时间为 O(n + 2n)，与 O(3n) 相同，并且由于 3 只是一个系数，因此复杂度为 Θ(n)。

这个分析准确吗？

Answer 1

是的，你的分析是正确的。计数排序的运行时间是 Θ(n + k)，其中 n 是元素的数量，k 是桶的数量。如果任何固定常数 c 的最大值是 cn，那么计数排序的运行时间将是 Θ(n)，正如您所提到的。

希望这可以帮助！