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

admin2019-01-16 54

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

选项

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

学硕统考专业

雅尔塔体系、两极格局、“冷战”三者的区别与联系是什么?

古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。

解放军渡江战役中横渡长江的东西两个攻击点是()。

下列哪一个不是罗马王政时代的管理机构?()

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

患儿，女，3岁。消瘦，“X”型腿，肋骨呈串珠状，“鸡胸”，方颅。X线提示：骨质疏松，掌、腕骨愈合缓慢。初步诊断

髓腔解剖特点对牙髓炎的意义中哪一点是错误的

依据《联合国海洋法公约》，军舰在公海上发现其他船舶有下列哪些嫌疑，可行使登临和检查的权利?()

OneSundaymorning,MillieandAmywenttoSunshinePark.Theylovetochatthere.Asusual,theysat【C1】______abigtree.Sudde

以教师为中心的策略主要是指班级授课制。()

下列教师行为违背法律的是()。

从批判传统的系统教育论出发，范例教学强调克服教材内容的繁琐，要求从日常生活中选取典型案例，并在教学内容上提出了基本性、基础性和范例性三条原则。其基本性原则，要求教给学生基本的知识结构，包括()。

GoldwasdiscoveredinCalifornia______.

PASSAGETHREEWhatcanbeconcludedfromthelastsentenceinPara.6?

Allpeoplehavesomeabilitytomanagetheirhealthandthehealthofthosetheycarefor.Meanwhile,withtheincreasingcomple