对n个元素从小到大排序……那么采用基于比较的排序,时间下界是?对n个元素从小到大排序,已将它们分成了n/k组,每组k个数.而且每组中的所有数都大于前一组的所有数.那么采用基于比较的排

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)