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

admin2019-08-01 64

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

在五四运动中，站在最前列，起了先锋作用的是()。

斯大林时期的经济体制最本质的特点是()。

下列不属于苏联高度集中的经济政治体制产生的条件的是()。

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

中世纪战争史上有过两次君士坦丁堡陷落，分别简述其发生的时间、征战的双方、导致的历史变动。

新文化运动前期的指导思想是()。

保加利亚共产党于1990年4月改名为保社会党，它在政府中沦为少数派的时间是()。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：我国银行最早的雏形是唐朝时期出现的()

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

关于磁共振图像矩阵与分辨力关系的描述，正确的是

A．玉女煎B．芍药汤C．龙胆泻肝汤D．清胃散E．凉膈散

目前我国的轻钢龙骨主要有两大系列，仿日本系列和仿欧美系列，关于它们的描述，错误的是()。

按预算编制形式可将政府预算分为()。

将下列各项按所表示年龄大小顺序排列，正确的顺序应是()。①不惑②垂髫③花甲④加冠⑤而立⑥古稀⑦半百

在诊断睾丸鞘膜积液时需要与哪些疾病相鉴别

设n维列向量组α1，α2，…，αm(m＜n)线性无关，则n维列向量组β1，β2，…，βm线性无关的充分必要条件是()．

TheUnitedStateshashistoricallyhadhigherratesofmarriagethanthoseofotherindustrializedcountries.Thecurrentannual

ThoughtsofsuicidehauntedAnitaRutnamlongbeforeshearrivedatSyracuseUniversity.Shehadahistoryofmentalillnessand