怎么可能桶排序的复杂度为O（n + k）的？ [英] How could the complexity of bucket sort is O(n+k)?
问题描述
在说：这已经被问过，或者找到一个算法书，请继续阅读并告诉我我的推理的一部分出了问题？
Before saying "this has been asked before", or "find an algorithm book", please read on and tell me what part of my reasoning went wrong?
假设你有n个intergers，你divded他们为k桶，这将需要O（n）的时间。然而，需要进行排序每个k个垃圾桶，如果使用快速排序每个箱，这是一个O（（N / K）*日志（N / K））的操作，所以这一步就需要为O（n *日志（ N / K）+ K）。终于有需要装配这个数组，这需要O（N + K），（见<一href="http://stackoverflow.com/questions/7311415/how-is-the-complexity-of-bucket-sort-is-onk-if-we-implement-buckets-using-lin">this张贴的），所以总的操作将是O（N + N *的log（n / k）的+ K）。现在，这究竟是怎么的n * log（N / K）消失了，我想不通的。我的猜测是有一定的数学去上消除了这种的n * log（N / K）。任何人都可以帮忙吗？
Say you have n intergers, and you divded them into k bins, this will take O(n) time. However, one need to sort each of the k bins, if using quick sort for each bin this is an O((n/k)*log(n/k)) operation, so this step would take O(n*log(n/k)+k). Finally one need to assemble this array, this takes O(n+k), (see this post), so the total operation would be O(n+n*log(n/k)+k). Now, how did this n*log(n/k) disappeared, I could not figure at all. My guess is there is some mathematics going on which eliminates this n*log(n/k). Anyone could help?
推荐答案
您的假设：
- K - 桶的数量 - 可以是任意
是错误的。
有水桶之类的两种变体，所以它是相当混乱。
There are two variants of bucket sort, so it is quite confusing.
A
桶的数目等于项目的数量在输入
The number of buckets is equal to the number of items in the input
请参阅分析这里
B
桶的数目等于的研究的 - 可能值的输入整数的数目
The number of buckets is equal to R - the number of possible values for the input integers
这篇关于怎么可能桶排序的复杂度为O（n + k）的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
