如果我们假设元素在给定的范围k内均匀分布,我们有10个桶。那么在对列表中的n个元素进行一次迭代之后,每个存储桶中的元素数量将是相同的。例如,我们使用快速排序对每个存储桶进行排序,但是我们知道每个存储桶中的元素数量是恒定的,那么总运行时间不是Θ(n)吗?
发布于 2015-11-18 22:45:37
不是的。
将元素放入10个桶中是O(N)。
使用qsort对一个存储桶进行排序的时间为O(NlogN) (实际上是N/10,但常量与复杂性无关)。
因此,总体复杂度将是O(N + 10 *N logN),即O( NlogN ) (因为N
如果这很难理解,请尝试这样做:如果有2个存储桶而不是10个,那么您将对整个列表进行精确的Qsort。
https://stackoverflow.com/questions/33779500
复制相似问题