首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
admin
2013-12-19
51
问题
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
选项
答案
假定特排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。若二叉树高度是h，则叶子结点个数最多为2
h-1
个；反之，若有u个叶子结点，则二叉树的高度至少有1og
2
u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为1og
2
(n!)的路径，即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)次。根据斯特林公式，有log
2
(n!)=()(nlog
2
n)，即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/aval777K
本试题收录于：
计算机专业知识题库事业单位考试分类
0
计算机专业知识
事业单位考试
相关试题推荐
教师备课需要做好三个方面的工作，包括()。
沟通教育者、受教育者、教育内容三者的桥梁是()。
对整个教学过程起着主导的、决定性作用的是()。
避免教学中的性别偏向有多个需要注意的方面。比如，在课堂上，教师要给予男女生同样多的注意，对男女生的提问次数、问题性质要差不多，对男女生所给予的反馈质量、数量也要相当。这里讲的是()。
下面是一位教师的反思日记。回顾过去，我感觉到，过去一个学期的教学比我前十年的教学总和都更能让我明白什么叫教育。以前，我教过好几个班，并且每班人数都在80左右。每天我的大部分时间都在备课，与学生的交流很少，我只考虑自己能提供什么，很少考虑学生需要什
我国明代教育家王阳明指出：“大抵童子之情，乐嬉游而惮拘检，如草木之始萌芽，舒畅之则条达，摧扰之则衰萎。今教童子，必使其趋向鼓舞，中心喜悦，则其进自不能已”。这句话涉及的教育原则是()。
教师道德范畴，从广义上讲，是指反映和概括有关教师道德现象的特征、方面和关系的各种基本概念。不但教师道德原则和规范所包含的基本概念可以看作教师道德范畴，就是反映教师个体道德行为和道德品质，以及道德评价、道德修养和道德教育等方面的概念，也可以看作教师道德范畴。
教师道德范畴，从广义上讲，是指反映和概括有关教师道德现象的特性、方面和关系的各种基本概念。不但教师道德原则和规范所包含的基本概念可以看作是教师道德范畴，就是反映教师个体道德行为和道德品质以及道德评价、道德修养和道德教育等方面的基本概念，也可以看作是教师道德
#include#includestructnode{inthum；structnode*next；}；structnode*create(structnode*head)
在路由器中，如果去往同一目的地有多条路由，则决定最佳路由的因素有()。
随机试题
在系类型中，系主和成员之间的联系是
患者28岁。不孕3年，月经5～6天/20～50，量中等，无痛经，妇科检查未见异常。进一步检查应首选
下列哪项表述与盐酸小檗碱的性质不符（）。
髋关节后脱位的典型体征是
二元函数f(x，y)=4(x-y)-x2-y2的极值为()。
多用户结构是指有多台微机，但每台微机都有相应的输入输出设备，每台微机仍属单机结构，各台微机不发生直接的数据联系(通过磁盘、光盘、U盘、移动硬盘等传送数据)。()
工厂的设计能力在()中需要明确。
在我国社会主义条件下，权力制约和监督的必要性表现为()。
三清山风景如画，有_________的峰峦，_________的奇石。填入划横线部分最恰当的一项是：
Everymorning,Alliewakesupandaccompaniesherfriendtothewashroom.Sheturnsonthelight,soapsupawashcloth,andbegi
最新回复
(
0
)
