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

admin2017-11-14 47

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

【朱熹】山西大学2012年中国古代史复试真题；西北大学2013年专门史真题；南开大学2014年日本史真题

《加施泰因协定》

【胡司战争】南京大学2006年世界近现代史真题

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

义和团爆发的直接原因是()。

汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。

“瓜步之战”发生在下列哪两个政权之间?()

下列对1918年德国十一月革命说法不正确的是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

可以用于判断两种商品或者服务是否具有替代关系或互补关系的指标是()。

导致艾滋病患者死亡的最常见的机会性感染是

大叶性肺炎肝变期，听诊肝变区内可闻()。

下列关于法律规范作用的说法正确的是()。

下列各项中，属于业务预算内容的有()。

【B1】【B10】

Insteadofbuyingacommercialbookkeepingsystem,theaccountantsofFullmanFinancedecidedtodesignoneof______.