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

admin2019-01-16 58

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

选项

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

学硕统考专业

唐太宗、武则天、唐玄宗(前期)都共同注意的问题是()

民族区域自治制度是在国家的统一领导下，在()实行民族区域自治，设立自治机关，行使自治制度。

下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

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

英国革命中。平等派的领导人是()。

A．左锁骨中线内侧第5肋间B．胸骨左缘第2肋间C．胸骨右缘第2肋间D．胸骨左缘第3肋间E．胸骨左缘第4～5肋间

在房地产价格评估中，重新建造成本是假设在______重新建造或购置全新状态的旧有房地产时所必要的成本或价格。

在建设项目决策阶段，业主方负责或者组织开展()。

在生产中，由于()所产生的噪声，称为生产性噪声或工作噪声。

梦是潜意识冲动和愿望的表现，是哪个学派的观点()。

在窗体上画一个名称为Command1的命令按钮和一个名称为Text1的文本框，然后编写如下事件过程：PrivateSubCommand1_Click()n=Val(Text1.Text)