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

admin2019-01-16 45

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

选项

答案假定待排序的记录有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/viRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

北宋时期，由于原有的市坊制度被打破，因此北宋政府控制商人和商业主要通过()。

沙俄企图侵占中国东北地区，制造“海兰泡惨案”的时间是（）。

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

8世纪中期，控制东自黑龙江，西到阿尔泰山广大地区的民族是()。

患者，男性，68岁，诊断慢性心力衰竭5年。3天前着凉后出现发热．且体重较平时增加近3公斤，护士评估其存在重度水肿，指导患者每日摄盐量不可超过

该企业集团的经营战略是()。牙膏在该公司的产品组合中是()。

工程造价咨询企业信用档案不包括()。

()是建设和巩固国防的基础，是增强民族凝聚力、提高全民素质的重要途径。

下列关于股权投资评估的评估，说法错误的是()。

某单位要从100名报名者中挑选20名献血者进行体检。最不可能被挑选上的是1993年以来已经献过血，或是1995年以来在献血体检中不合格的人。如果上述断定是真的，则以下哪项所言及的报名者最有可能被选上?

设f(x，y)=kx2+2kxy+y2在点(0，0)处取得极小值，求k的取值范围．

宏操作SetValue可以设置

Educatorstodayaremoreandmoreoftenheardtosaythatcomputerliteracyisabsolutelynecessaryforcollegestudents.Manye