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

admin2019-08-15 41

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

明清时期专制主义空前加强，据此回答问题：清代在散文方面，声势最大、影响最广的是桐城派，不属于该派的是()

米勒兰事件

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

以下关于CPU的叙述中，错误的是()。

（2019年聊城茌平区）学生作为一种影响因素，主要从（）两方面影响学与教的过程。

领导者影响力的来源有职位权力与个人权力，下列属于职位权力的是()

下列属于毛泽东新民主主义革命理论的内容有()

Thereasonwhyhefailedintheexamwasthathewasoftenabsent-mindedinclass.

关于生长发育的规律，不正确的描述是()

下列关于注销工程监理企业资质情形的说法，正确的有()。

目前国内普遍实行的()模式决定了劳务分包的普遍性。

下列关于模式分解的叙述中，正确的是

铜鼓(bronzedrum)文化是中国南方地区典型的文化代表。在古代，铜鼓多用于祭拜、出征仪式(deploy-ingritual)和庆祝活动。它是激动人心的打击乐器(percussioninstrument)，给人们带来极大的精神鼓舞。在战场上，铜鼓