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

admin2019-08-15 49

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

选项

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

学硕统考专业

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题最后废除节度使的是()

1977年4月，对“两个凡是”提出批评，开全党思想解放先河的是()。

重庆谈判签署的文件是()。

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

相对于单一内核结构，采用微内核结构设计实现操作系统具有诸多好处，但是，()并不是微内核的优势。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；

在“青年是祖国的未来”和“青年应该奋发向上”两语句中，概念“青年”()

路基工程施工组织设计应重点考虑的内容有()。

单位要想从事吸收公众存款等商业银行业务，在名称中使用“银行”字样，要经过()批准。

根据《中华人民共和国民事诉讼法》，下列行为引发的纠纷中，权利人可以申请支付令的有()。

与银行借款相比，下列各项中，不属于融资租赁筹资特点的是()。

核对、商定日程的过程中，若对方提出修改意见或要求增加新的游览项目，地陪的正确处理方法是()

“鱼缸法则”是指成长需要自由的空间，要使人成长的更快，就一定要给他活动的自由，而不是将他拘泥在一个小小的鱼缸中。根据上述定义，下列符合“鱼缸法则”的是：

根据下面材料回答下列题。2006年农村居民人均纯收入比2007年农村居民人均纯收入少()。

Thenextgreatlandareathatmanhopestocolonizeisthemoon.InsizeitisnearequaltotheareaofNorthand