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

admin2014-01-13 40

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

理想的师生关系具备以下几个特征?()

关于课程与教材编制、课程与教学实施、课程与教学评价等，下列说法中错误的是()。

习近平总书记要求大力弘扬中华民族勤俭节约的优秀传统，努力使厉行节约、反对浪费在全社会蔚然成风。提出“节俭”“节用”主张的中国古代思想流派是()。

教育目的具有层次性，其结构包括()。

【2015年菏泽市真题】遗传对儿童发展有重要的作用，但影响儿童发展的后天因素主要是营养、睡眠和适宜的运动。()

4G是集3G与WLAN于一体，能够以100Mbps以上的速度下载，加快传输高质量音频、视频图像，几乎能满足所有用户对于无线服务要求的第四代移动通信技术。4G手机传递信息依靠的是()。

Word“自动保存”功能可以每隔一定时间保存一次文档，自动保存以后可用于断电恢复。但不能代替正常存盘。()

某公司为了寻找改进管理的途径召开头脑风暴法的会议。在会议上大家各抒己见，但是少数人提出的方法荒诞不经，甚至有时让人感觉离题太远。对于这种情况你应该如何处理?()

在Word编辑状态下，建立了一个由多个行和列组成的表格。如果选中一个单元格，再按Delete键，则()。

下列技术合同中关于技术成果权归属说法正确的是()

保险合同的关系人包括()

由于资本市场线通过无风险资产[点(0，rF)]及市场组合M[点(σM，E(rM)]，于是资本市场线的方程可以表示为：则下列说法正确的是()。

一般纳税人零售下列商品可以开具增值税专用发票的是()。

依次填入下列横线上的词语，最恰当的一项是()。①当春天到来时，百花盛开，各自争相斗艳，一派繁荣。当夏天到来时，满池荷花，蝉鸣伴奏，。②凶猛的网络经济着传统媒体，差不多已经击垮了传统书店。

明星：炒作：绯闻

There’sacommonwarningaboutourplanet’sfuture;theriskoffoodshortages."We’vegotagrowingworldandahungryworld.W

若对一个已经排好了序的序列进行排序，在下列4种方法中，哪一种方法比较好?

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

计算机专业知识

事业单位考试

理想的师生关系具备以下几个特征?()

关于课程与教材编制、课程与教学实施、课程与教学评价等，下列说法中错误的是()。

习近平总书记要求大力弘扬中华民族勤俭节约的优秀传统，努力使厉行节约、反对浪费在全社会蔚然成风。提出“节俭”“节用”主张的中国古代思想流派是()。

教育目的具有层次性，其结构包括()。

【2015年菏泽市真题】遗传对儿童发展有重要的作用，但影响儿童发展的后天因素主要是营养、睡眠和适宜的运动。()

4G是集3G与WLAN于一体，能够以100Mbps以上的速度下载，加快传输高质量音频、视频图像，几乎能满足所有用户对于无线服务要求的第四代移动通信技术。4G手机传递信息依靠的是()。

Word“自动保存”功能可以每隔一定时间保存一次文档，自动保存以后可用于断电恢复。但不能代替正常存盘。()

某公司为了寻找改进管理的途径召开头脑风暴法的会议。在会议上大家各抒己见，但是少数人提出的方法荒诞不经，甚至有时让人感觉离题太远。对于这种情况你应该如何处理?()

在Word编辑状态下，建立了一个由多个行和列组成的表格。如果选中一个单元格，再按Delete键，则()。

下列技术合同中关于技术成果权归属说法正确的是()

保险合同的关系人包括()

由于资本市场线通过无风险资产[点(0，rF)]及市场组合M[点(σM，E(rM)]，于是资本市场线的方程可以表示为：则下列说法正确的是()。

一般纳税人零售下列商品可以开具增值税专用发票的是()。

依次填入下列横线上的词语，最恰当的一项是()。①当春天到来时，百花盛开，各自争相斗艳，一派繁荣。当夏天到来时，满池荷花，蝉鸣伴奏，________。②凶猛的网络经济________着传统媒体，差不多已经击垮了传统书店。

明星：炒作：绯闻

There’sacommonwarningaboutourplanet’sfuture;theriskoffoodshortages."We’vegotagrowingworldandahungryworld.W

若对一个已经排好了序的序列进行排序，在下列4种方法中，哪一种方法比较好?

依次填入下列横线上的词语，最恰当的一项是()。①当春天到来时，百花盛开，各自争相斗艳，一派繁荣。当夏天到来时，满池荷花，蝉鸣伴奏，。②凶猛的网络经济着传统媒体，差不多已经击垮了传统书店。