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

admin2019-08-01 72

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

罗马法的集大成《查士丁尼民法大全》产生的时间是在()。

完整地表述电磁场理论的物理学家是()。

二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。

下列不属于苏联高度集中的经济政治体制产生的条件的是()。

根据1931年的威斯敏斯特法，英国()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

关于清代我国疆域的叙述，下列()不正确。

新文化运动前期的指导思想是()。

对三国鼎立局面的形成起到关键性作用的战役是()。

两个以上污染者污染环境造成他人损害的，污染者承担

血清促胃液素增高伴胃酸缺乏的是

机体各种功能活动所消耗的能量中，最终不能转化为体热的是

下列哪项疾病的临床症状一般不是外阴瘙痒

三叉神经痛的药物治疗最有效的是

最好与铁剂同时服用的药物是

《建设工程质量管理条例》规定，施工单位必须按照工程设计要求、施工技术标准和合同约定，对()进行检验，检验应当有书面记录和专人签字；未经检验或者检验不合格的，不得使用。

某房地产开发企业拟开发建设一个由十幢住宅、一幢幼儿园和一幢物业服务中心组成的住宅小区。该住宅小区包括()。

数据库恢复属于商品流通企业数据库管理系统功能中()功能。