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

Question

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

假设您有 n 个整数，并将它们分成 k 个箱子，这将花费 O(n) 时间。但是，需要对 k 个 bin 中的每一个进行排序，如果对每个 bin 使用快速排序，这是一个 O((n/k)log(n/k)) 操作，因此此步骤将花费 O(nlog(n/k)+k)。最后需要组装这个数组，这需要 O(n+k)，(请参阅 this post )，因此总操作将是 O(n+nlog(n/k)+k)。现在，这个 nlog(n/k) 是怎么消失的，我完全想不通。我的猜测是有一些数学运算可以消除这个 n*log(n/k)。有人可以帮忙吗？

Answer 1

你的假设:

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

错了。

桶排序有两种变体，所以很容易混淆。

---

一个

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

见分析here

---

B

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

见分析here和 here