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

admin2019-01-16 57

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

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

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

世界天文史上最早实地测量子午线的记录是由谁进行的?()

就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。

下图是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)

经皮肝穿胆管造影前注射维生素K的主要目的是

上消化道大量出血

氯化锶四氢硼钠

依据《INCOTERMS2000》的规定，仅适用海上运输方式的贸易术语有()。

甲公司是国内一家印刷机制造企业，主要产品是胶印机。受不利大环境的影响，原有业务经营持续低迷。为此，公司董事会决定并购一家手游公司进军网络游戏。下列选项中，属于该企业采用多元化经营的优点有()。

人民警察的组织纪律包括不得参加罢工。()

判断、升级、意向、联系、交通

在数据库应用系统设计中，如果在事务中存在和用户的长时间交互，它会带来哪些坏处()。Ⅰ．降低系统的并发度Ⅱ．增加死锁的数量Ⅲ．破坏数据的一致性Ⅳ．影响检查点的效果

FromthewayyouaretalkingIcanonly______theconclusionthatyouarenottheslightestbitinterestedintheproject.