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

admin2019-08-15 31

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

提出电磁感应定律的是物理学家()。

唐朝时期，每丁服徭役二十天，是为正役，国家若不需要其服役，则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准，交足二十天的数额以代役，称为()。

米勒兰事件

中山舰事件

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45纳秒，主存的存取周期为200纳秒。已知在一段给定的时间内，CPU共访问内存4500次，其中340次访问主存。问：(1)Cache的命中率是多少?(2)CPU访问内存的平均

float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中，且x=一8．25，则FRl的内容是____。

关于颈淋巴管瘤CT表现的描述，错误的是

口腔黏膜下纤维化上皮表现不包括

港口工程施工合同规定，属于()的情况，承包商可以获得工程延期。

数据审核员不能由()兼任。

关于瑞文测验操作注意事项，下列说法中正确的是()。

《国家中长期教育改革和发展规划纲要(2010-2020年)》提出，未来十年国家教育发展的强大动力是()。

张三与李四有仇。某日，张三见李四前往公用水井打水，便抢先一步在水井中下毒，结果导致李四饮水后死亡。张三的行为已构成故意杀人罪。()

下列叙述中，正确的是()。

Thereisnomorefashionablesolutiontothecurrentglobalrecessionthan"greenjobs."Manycountriesarealleagerlypromotin