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

admin2014-01-13 62

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

选项

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

解析

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

本试题收录于：计算机专业知识题库事业单位考试分类

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

回归教育是一种教育理论，它认为人的一生应是学习和工作不断交替、相互结合的过程。接受义务教育或基础教育乃至高等教育后就业的成年人，应在需要时有机会返回学校去学习。下列教育类型属于回归教育的是()。

表示传统师德非常重视严于律己、身体力行、为人表率的模范作用的先哲名言是()。

党的十八大强调，建设中国特色社会主义，总依据是社会主义初级阶段，总布局是五位一体，总任务是实现社会主义现代化和中华民族伟大复兴。以下不属于五位一体建设的是()。

教师在教学中即使出现了错误，也不要坦率承认、及时改错，否则会影响教师威信。()

教育者对学生进行系统的马列主义和毛泽东思想的教育，并有目的地组织学生开展道德实践活动，这符合德育的()。

我国长期以来的教育传统是把()放在中心位置。

关于课程标准叙述不正确的是()。

计算机网络是计算机技术和多媒体技术密切结合的产物。（）

A、HugeStorm.B、Earthquake.C、Snowslide.D、Disappearanceoflivingspecies.D新闻中指出，气候的不断变暖会使一些地区的降雨量急速下降。而有些地方却洪水泛滥，世界上一半的动植物灭绝

患者，女性，53岁。胸闷、气急3周，胸片示右侧大量胸腔积液，胸穿抽出血性胸水1000ml。胸腔穿刺抽液时，患者出现头晕、出汗、面色苍白、四肢发凉，应立即

口腔预防科在某学校人群中验证一种含氟牙膏的防龋效果，对于研究方案的几个问题经讨论后确定下来。实验对象用的学生年级是

请简述药品分类管理的内容。

以承包商为某项索赔工作支付的实际开支为依据，向业主要求费用补偿的计算工程索赔的方法是()。

企业采用汇兑结算方式购入M材料一批，发票及账单已收到，增值税专用发票上记载的货款为80000元，增值税税额为13600元，支付保险费2000元，材料尚未到达。下列账务处理中，错误的有()。

该批免费补偿货物进口时，其报关单”贸易方式”栏应填：被更换的原进口货物退运出境时，海关对税费的征收是：

关于内幕信息和内幕交易，下列说法正确的是()。

431，325，()，167，844，639。

InputBox函数的返回值类型是（）。