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

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

为什么?要详细!
展开
 我来答
vbtraz
2011-10-15 · TA获得超过5532个赞
知道大有可为答主
回答量:4152
采纳率:0%
帮助的人:4440万
展开全部
既然分成了n/k组, 每个组之间又不需要排, 如果排序每个组的时间下界是f(k), 那么总的时间下界就是n/k* f(k)

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

所以总的时间下界就是 O(n/k * k logk) = O(nlog k)
yfhnb
2011-10-15
知道答主
回答量:24
采纳率:0%
帮助的人:15万
展开全部
算法中的一个定理:任意一个比较排序算法在最坏的情况下,都要做O(nlogn)次比较,所以时间下界为:n/k*klogk=nlogk
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式