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

admin2019-01-16 26

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

有人说，巴黎和会是一次分赃会议，下列《凡尔赛和约》中哪一方面的内容最能体现这一性质?()。

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

概述罗马共和国早期平民反贵族斗争的原因、过程和意义。

简述金帐汗国的统治措施。

《蒙巴顿方案》

在意大利统一过程中，加富尔为了获得拿破仑三世的支持，让与法国的领土是()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

现存迈锡尼线形文字B的材料绝大多数叙述的是迈锡尼的()

下列关于塞尔维乌斯改革的叙述中，不正确的是()。

格拉古兄弟改革

财务报表的编制基础是指财务报表是在持续经营基础上还是非持续经营基础上编制的。（）

现成偏误是指根据个别现成的事例来直接推导普遍规律，从而形成偏误认识的认知方式。根据上述定义，以下不属于现成偏误的是：

患者，女，61岁。左下颌颈部肿痛5日，伴发热，无寒战，诊断为急性蜂窝织炎，其最危险的后果是()

下列哪些选项属于设计单位的质量责任和义务?

A、 B、 C、 D、 C

苏格拉底法

Whatisthewoman’sattitudetowardeachofthefollowingactivitiesofstudy?ChooseFOURanswersfromtheboxandwritetheco

Whatwillthewomandotomorrow?