假设我们有一个数组，我们知道所有元素都是 0...2n 并且没有排序。
如果我们使用复杂度为 O(n+k) 的桶排序算法，其中 k 是元素的范围，在本例中为 2n，那么对该数组进行排序的复杂度是否为 θ(n)？
我的理由是，运行时间是 O(n + 2n)，它与 O(3n) 相同，并且由于 3 只是一个系数，因此复杂度为 θ(n)。
这个分析准确吗？
最佳答案
是的，你的分析是正确的。计数排序的运行时间是 θ(n + k)，其中 n 是元素的数量，k 是桶的数量。如果对于任何固定常数 c 来说最大值是 cn，那么计数排序的运行时间将为 θ(n)，正如您所提到的。
希望这有帮助!
关于arrays - 已知上限的桶排序的复杂性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19609547/