利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。

admin2019-08-15 54

问题利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。

选项

答案假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2^h-1；反之，若有u个叶子结点，则二叉树的高度至少为(log₂u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log₂(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log₂(n!)。根据斯特林公式，有log₂(n!)=O(nlog₂n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog₂n)。提示：此题考查的知识点是基于比较的排序算法效率。

解析

转载请注明原文地址:https://kaotiyun.com/show/jKCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：金文是指()

书院制度，始于唐而盛于宋，根据所学知识。回答问题：北宋最著名的四大书院是()

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：对于二里头文化的发现的意义，下列选项表述最准确的是()

下列选项中，不属于西汉农业发展状况的是()

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

下列几种排序方法中，要求内存量最大的是()。

某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45纳秒，主存的存取周期为200纳秒。已知在一段给定的时间内，CPU共访问内存4500次，其中340次访问主存。问：(1)Cache的命中率是多少?(2)CPU访问内存的平均

规定着家长的教育态度和行为的是家长的()

保兑行________

采用随机抽样的方法抽取某班10名中学生，调查本班的英语成绩。10名学生的英语成绩分别为85，90，76，94，82，91，88，80，96，89，计算这10名中学生的英语平均成绩是

维持子宫于盆腔正中位置，主要依靠

关于商标注册的说法，错误的是()。

《建设工程安全生产管理条例》规定，（）等自升式架设设施的使用达到国家规定的检验检测期限的，必须经具有专业资质的检验检测机构检测。经检测不合格的，不得继续使用。

项目风险管理过程包括：①项目风险对应；②项目风险评估；③项目风险识别；④项目风险监控。则正确的管理流程是()。

设ξ为f(x)=arctanx在[0，a]上使用微分中值定理的中值，则为().

Fromhervantagepointshewatchedthemaindoorsswingopenandthefirstarrivalspourin.Thosewhohadbeenattheheadoft