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

admin2017-11-14 40

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

武昌起义()。①由同盟会直接领导②原计划被偶然因素打乱③其成功有深刻的社会原因④迅速的胜利潜伏着失败的危机

“瓜步之战”发生在下列哪两个政权之间?()

美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场

中华人民共和国恢复在联合国合法席位的时间是()。

文艺复兴运动兴起的时间是()。

下面哪项条约没有涉及德国的赔款问题?()

周王室的两大官僚系统是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

在集中式总线仲裁中，()方式响应时间最快。

计算机系统总线包括①地址总线、②数据总线和③控制总线。若采用DMA方式传送数据，需要DMA控制器控制的是()。

视神经鞘膜常发生的病变为

依据法律的规定，在管制的判决和执行方面，下列说法哪些是不正确的?()

银行依法为单位、个人在银行开立的()保密，维护其资金的自主支配权。

金融市场的功能有()。

王平是凤凰公司的经理，李强的所有朋友都在凤凰公司工作。胡斌是李强的朋友。凤凰公司中有些职工来自湖南，凤凰公司所有的职工都是大学生。据此，我们可以知道

Itwasrecommendedthatwe______fortheauthorities.

在数据库逻辑结构设计中，将E-R模型转换为关系模型应遵循相应原则。对于三个不同实体集和它们之间的一个多对多联系，最少应转换为多少个关系模式?

如果一个教师可以讲授多门课程，一门课程可以由多个教师来讲授，则教师与课程存在的联系是()。