桶排序的复杂度怎么会是O(n+k)呢？

在说“这个问题以前有人问过”或者“找一本算法书”之前，请继续阅读并告诉我我的推理的哪一部分出了问题？

假设你有 n 个整数，并将它们分成 k 个容器，这将花费 O(n) 时间。然而，需要对 k 个 bin 中的每一个进行排序，如果对每个 bin 使用快速排序，则这是 O((n/k)log(n/k)) 操作，因此这一步将花费 O(nlog(n/k)+k)。最后需要组装这个数组，这需要 O(n+k)，（参见这个帖子 https://stackoverflow.com/questions/7311415/how-is-the-complexity-of-bucket-sort-is-onk-if-we-implement-buckets-using-lin)，所以总的操作将是 O(n+nlog(n/k)+k)。现在，这是怎么做到的？log(n/k) 消失了，我根本无法弄清楚。我的猜测是有一些数学运算可以消除这个 n*log(n/k) 。有人可以帮忙吗？

你的假设：

• k - 桶的数量 - 是任意的

是错的。

桶排序有两种变体，所以很混乱。

A

桶的数量等于输入中项目的数量

查看分析here http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm

B

桶的数量等于R- 输入整数的可能值的数量

查看分析here http://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-23.html and here http://www.ics.uci.edu/~eppstein/161/960123.html