首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
63
问题
利用比较的方法进行排序,在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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
学硕统考专业
相关试题推荐
试评述明末清初三大思想家顾炎武、黄宗羲、王夫之。
中华人民共和国恢复在联合国合法席位的时间是()。
下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
下列选项中,控制了西域政权的是()。
战国初期,上党地区在下列哪一个国家的控制范围之内()。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
CISC与RISC的区别表现在()。
随机试题
投保人王某勾结鉴定人朱某故意提供虚假的证明文件,使得王某获得了巨额保险金对王某和朱某的行为如何处罚?( )
下列关于地图比例尺的说法中,正确的有()。
青铜器的冶炼和铸造技术达到很高水平是在()时代。
某选区在举行人民代表大会代表直接选举时,应参加选举的选民为25000人,实际参加选举的选民为12350人。该选区三位候选人甲、乙、丙最后实际获得选票依次为6250票、3500票、2600票。依照法律规定,选举结果是()。
中共十八大以来,以习近平为总书记的新一届中央领导集体,带领全党全国各族人民积极应对前进道路上的困难和挑战,更好落实发展这个党执政兴国的第一要务。经济发展进入新常态,要坚持以提高发展质量和效益为中心,切实()。
公路客运方面:10月5日共发送客车3546车次,发送旅客5.45万人次;抵达客车1472车次,抵达旅客1.88万人次。民航方面:10月5日共发送航班236班次,发送旅客3.25万人次;抵达航班233班次,抵达旅客2.83万人次。[img][/img]
“文化-历史”发展理论的创始人是
Tounderstandthemarketingconcept.itisonlynecessarytounderstandthedifferencebetweenmarketingandselling.Nottooman
AddisonHeardusesanimageofhiswifeandinfantsonforthebackgroundonhislaptop.AnMBAstudentattheUniversityofVir
A、Itcanbevalidforsevendays.B、Ayearlypasscostsonly$18.C、Itvariesindifferentseasons.D、Itisfreeforpeopleover
最新回复
(
0
)