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

admin2013-12-19 58

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

选项

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

解析

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

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

属于了解学生的方法的是()。

学校管理过程的中心环节是()。

《基础教育课程改革纲要(试行)》指出，基础教育课程评价改革的目标是()。

为了解决名词与术语脱离事物、抽象概念脱离具体形象、理解脱离感知等矛盾，教师在教学时应该注意贯彻()。

水是由氢、氧两种元素组成的物质。所谓硬水和软水的物质，就是水中含有钙、()化合物多少的程度区别。

【2015年菏泽市真题】心理学家的研究表明，所有的初中学生都达到了形式运算阶段。()

#include#includetypedefstructstudent{inthum；charnameE20]；charsex；mtage；}LIST；LIST*

一台主机或路由器同因特网有多个接口，为保证唯一性，其只能拥有一个IP地址。()

焦点方位特性对有效焦点大小分布的描述，正确的是

小儿易患感冒、咳嗽、哮喘及时行诸病的主要因素是()

下列说法中错误的是(　　)。

甲、乙、丙拟设立一家有限责任公司，注册资本为30万元，在甲、乙、丙订立的协议中约定：甲以现金人民币10万元出资，乙以商标权作价4万元出资，丙以专利权作价16万元出资。甲、乙、丙出资的约定符合法律规定。()

某企业由于采用了不同的存货计价方法，使得期末存货计价高估5000元，如果不考虑其他影响，这会使得当期损益()。

根据“格雷欣法则”，当市场上流通两种法定金融货币时，最终可能会使市场上()。

公文标题一般由()组成。

患者，女性，50岁。因“口内多数牙齿缺失，要求修复”，来医院治疗。患者平躺在治疗椅上，在检查过程中，发现患者口腔在不说话、不咀嚼，不吞咽时，上下颌牙弓脱离接触。此时，患者下颌所处的位置是()。

设a，b，c均为正数，且a+d=6+c，|a-d|

Thepurposeofany【C1】______interviewistochoosetherightpersonforthejobinquestionortoselectsomeonewhoshowspot

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

计算机专业知识

事业单位考试

属于了解学生的方法的是()。

学校管理过程的中心环节是()。

《基础教育课程改革纲要(试行)》指出，基础教育课程评价改革的目标是()。

为了解决名词与术语脱离事物、抽象概念脱离具体形象、理解脱离感知等矛盾，教师在教学时应该注意贯彻()。

水是由氢、氧两种元素组成的物质。所谓硬水和软水的物质，就是水中含有钙、()化合物多少的程度区别。

【2015年菏泽市真题】心理学家的研究表明，所有的初中学生都达到了形式运算阶段。()

#include#includetypedefstructstudent{inthum；charnameE20]；charsex；mtage；}LIST；LIST*

一台主机或路由器同因特网有多个接口，为保证唯一性，其只能拥有一个IP地址。()

焦点方位特性对有效焦点大小分布的描述，正确的是

小儿易患感冒、咳嗽、哮喘及时行诸病的主要因素是()

下列说法中错误的是( )。

甲、乙、丙拟设立一家有限责任公司，注册资本为30万元，在甲、乙、丙订立的协议中约定：甲以现金人民币10万元出资，乙以商标权作价4万元出资，丙以专利权作价16万元出资。甲、乙、丙出资的约定符合法律规定。()

某企业由于采用了不同的存货计价方法，使得期末存货计价高估5000元，如果不考虑其他影响，这会使得当期损益()。

根据“格雷欣法则”，当市场上流通两种法定金融货币时，最终可能会使市场上()。

公文标题一般由()组成。

患者，女性，50岁。因“口内多数牙齿缺失，要求修复”，来医院治疗。患者平躺在治疗椅上，在检查过程中，发现患者口腔在不说话、不咀嚼，不吞咽时，上下颌牙弓脱离接触。此时，患者下颌所处的位置是()。

设a，b，c均为正数，且a+d=6+c，|a-d|

Thepurposeofany【C1】______interviewistochoosetherightpersonforthejobinquestionortoselectsomeonewhoshowspot

下列说法中错误的是(　　)。