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

admin2019-01-16 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/glRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争。这一古老文件是()

改革开放以后，我国农村产业结构巨大的转变表现在()。

陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()

论述秦国商鞅变法的内容、过程以及重要意义。

秦统一过程中，最先和最后灭掉的国家是()。

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

简述按照恩格斯的划分方法人类的起源与进化。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

利用环境容量排污者的义务包括：、、、、__。

不引起生理性瞳孔缩小的是

一个无症状的18岁大学新生，男，在体格检查中发现血压148／90mmHg，眼底检查正常。尿蛋白++，以下哪一种情况最可能存在

我国的中央银行是()。

中间汇率是()。

公安工作是我国(　　)的重要组成部分。

当前下列国家中，国民用于购买食物费用占口常支出平均比重最高的是：

Inrecentyears,manyAmericansofbothsexesandvariousageshavebecomeinterestedinimprovingtheirbodies.Theyhavebecom

Youwillnowbeaskedaquestionaboutafamiliartopic.Afteryouhearthequestion,youwillhave15secondstoprepareyourr

Hehasneverreally______theshockofhisson’sdeath.

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

计算机408

学硕统考专业

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争。这一古老文件是()

改革开放以后，我国农村产业结构巨大的转变表现在()。

陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()

论述秦国商鞅变法的内容、过程以及重要意义。

秦统一过程中，最先和最后灭掉的国家是()。

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

简述按照恩格斯的划分方法人类的起源与进化。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

利用环境容量排污者的义务包括：______、______、______、______、______。

不引起生理性瞳孔缩小的是

一个无症状的18岁大学新生，男，在体格检查中发现血压148／90mmHg，眼底检查正常。尿蛋白++，以下哪一种情况最可能存在

我国的中央银行是()。

中间汇率是()。

公安工作是我国( )的重要组成部分。

当前下列国家中，国民用于购买食物费用占口常支出平均比重最高的是：

Inrecentyears,manyAmericansofbothsexesandvariousageshavebecomeinterestedinimprovingtheirbodies.Theyhavebecom

Youwillnowbeaskedaquestionaboutafamiliartopic.Afteryouhearthequestion,youwillhave15secondstoprepareyourr

Hehasneverreally______theshockofhisson’sdeath.

利用环境容量排污者的义务包括：、、、、__。

公安工作是我国(　　)的重要组成部分。