Question

对n个元素从小到大排序……那么采用基于比较的排序，时间下界是？

对n个元素从小到大排序，已将它们分成了n/k组，每组k个数。而且每组中的所有数都大于前一组的所有数。那么采用基于比较的排序，时间下界是（B）
A.O(nlogn) B. O(nlogk) C. O(klogn) D. O(klogk)

为什么？要详细！

Answer 1

既然分成了n/k组， 每个组之间又不需要排， 如果排序每个组的时间下界是f(k)， 那么总的时间下界就是n/k* f(k)

所以其实问题就是排序包含k个数的数组的时间下界是什么， 不清楚这个怎么定义的， 要我说排序k个数的时间下界就是O(k)，当它们正好是有序的， 只要比较k-1次就可以确认这一点。 但是按题目意思应该说的是，最有效的算法的时间开销，那么就是 O(klogk)

所以总的时间下界就是 O(n/k * k logk) = O(nlog k)

Answer 2

算法中的一个定理：任意一个比较排序算法在最坏的情况下，都要做O(nlogn)次比较，所以时间下界为：n/k*klogk=nlogk