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

admin2019-08-15 32

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

选项

答案假定待排序的记录有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://jikaoti.com/ti/WMGjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题最后废除节度使的是()

义和团发展到高潮的标志是()

波士顿倾茶事件

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

在一个双链表中，在p结点之前插入q结点的操作是()。

路由器采用()方式来发送IP分组。

计算机系统采用补码运算是为了()。

下面关于进程的叙述中，正确的是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

患者，男性，37岁，建筑工人，装修时不慎触电，心跳呼吸骤停来院急诊，迅速心肺复苏。心脏复苏按压的部位是

营销环境由微观环境和宏观环境组成。宏观环境是指能影响整个微观环境的广泛的社会性因素，包括()。

分保分出人与分保接受人签订分保合同，以保险金额的一定比例承担保险责任，这种再保险被称为()。

下列选项中，表述不正确的是()。

发展顺序量表可以告诉人们某儿童的发育与其年龄相比()。

学校教学工作的基本组织形式是()。

【2014年广东深圳】未成年人不分()等，依法平等地享有权利。

法律关系是由法律规范调整的，以主体间权利和义务为内容的特殊社会关系。下列行为中不能形成法律关系的是()。

如果豌豆汤和酸模汤在周一提供，那么下列哪一项可以是真的?()如果周一只提供豌豆汤，周五只提供面汤，那么下列各项都可以是真的，除了：()

简述问题解决的含义及心理过程。

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

计算机408

学硕统考专业

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题最后废除节度使的是()

义和团发展到高潮的标志是()

波士顿倾茶事件

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

在一个双链表中，在*p结点之前插入*q结点的操作是()。

路由器采用()方式来发送IP分组。

计算机系统采用补码运算是为了()。

下面关于进程的叙述中，正确的是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

患者，男性，37岁，建筑工人，装修时不慎触电，心跳呼吸骤停来院急诊，迅速心肺复苏。心脏复苏按压的部位是

营销环境由微观环境和宏观环境组成。宏观环境是指能影响整个微观环境的广泛的社会性因素，包括()。

分保分出人与分保接受人签订分保合同，以保险金额的一定比例承担保险责任，这种再保险被称为()。

下列选项中，表述不正确的是()。

发展顺序量表可以告诉人们某儿童的发育与其年龄相比()。

学校教学工作的基本组织形式是()。

【2014年广东深圳】未成年人不分()等，依法平等地享有权利。

法律关系是由法律规范调整的，以主体间权利和义务为内容的特殊社会关系。下列行为中不能形成法律关系的是()。

如果豌豆汤和酸模汤在周一提供，那么下列哪一项可以是真的?()如果周一只提供豌豆汤，周五只提供面汤，那么下列各项都可以是真的，除了：()

简述问题解决的含义及心理过程。

在一个双链表中，在p结点之前插入q结点的操作是()。