首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
33
问题
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个,则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子,则说明尚有两种状态没有分辨出来。我们知道,若二又树高度是h,则叶子结点个数最多为2
h-1
;反之,若有u个叶子结点,则二叉树的高度至少为(log
2
u)+1。这就是说,描述n个记录排序的判定树必定存在一条长度为log
2
(n!)的路径。即任何一个借助“比较”进行排序的算法,在最坏情况下所需进行的比较次数至少是log
2
(n!)。根据斯特林公式,有log
2
(n!)=O(nlog
2
n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。 提示:此题考查的知识点是基于比较的排序算法效率。
解析
转载请注明原文地址:https://kaotiyun.com/show/viRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
两宋之交活跃于太行山一代,脸上刺有“赤心报国,誓杀金贼”的一支义军是()。
唐太宗、武则天、唐玄宗(前期)都共同注意的问题是()
从20世纪50年代开始,西欧和日本资本主义经济持续发展的共同原因是()。①政府都推行了一些社会改革,促进了经济发展②都注重发展或引进先进的科学技术、提高劳动生产率③都重视发展教育,培养人才④都接受了国外大量订货,刺激了经济发展
试论春秋战国时期思想文化获得发展的主要原因。
春秋战国时期,提出“祸兮福之所倚,福兮祸之所伏”的思想家是()。
冶铁技术中的淬火法提高了铁器的坚韧与锋利程度,这一技术最早出现在()。
西周统治者提出的天命思想和与此相应的治国思想分别为()。
下列政权中,控制西域的政权是()。
周王室的两大官僚系统是()。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
随机试题
对于“明星”型的经营单位,企业应该采取的战略是()。
贾某与家人到宏宇餐厅就餐。该餐厅所提供的卡式炉是由某用具厂生产的,卡式炉所使用的燃气是由某燃气公司生产的,贾某与家人在用餐时,正在使用的卡式炉和燃气罐发生爆炸,致使贾某面部、双手烧伤。共花去医疗费等财产损失7万元,经查:燃气公司以及用具厂生产的燃气和炉子均
阑尾动脉发自()
影响微囊中药物释放速度的因素不包括
患者,女,23岁。被人发现时呈昏迷状态。查体:神志不清,两侧瞳孔呈针尖样大小,呼吸有大蒜臭味。应首先考虑的是()
月度财务会计报告的保管期限为()年。
侵犯他人生命健康权的,应当承担()。
甲装修公司欠乙建材商场货款5万元,乙商场需付甲公司装修费2万元。现甲公司欠款已到期,乙商场欠费已过诉讼时效,甲公司欲以装修费充抵货款。下列哪一种说法是正确的?
当炫耀式旅游成了目的,扎堆往知名景点挤,也就在意料之中。其实旅游作为一种现代的生活方式,可以有多样化的功能。如果是为了教育,可以带孩子去看看名山大川、古城遗迹,帮助他们了解国家的历史和文化传统;如果是为了休闲放松,可以去海边、深山、或者就近选择市郊的农家小
HarvardUniversity,breakingwithamajortrendincollegeadmissions,willeliminateitsearlyadmissionsprogramnextyear,wi
最新回复
(
0
)