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

admin2014-01-13 78

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

选项

答案假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。若二叉树高度是h，则叶子结点个数最多为2h-1个；反之，若有u个叶子结点，则二叉树的高度至少有log2tl+1。这就是说，描述n个记录排序的判定树必定存在一条长度为Iog2(n!)的路径，即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少。根据斯特林公式，有lOg2(n!)=(nlg2r1)，即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为(nlog2r1)。

解析

转载请注明原文地址:https://kaotiyun.com/show/PZal777K

本试题收录于：计算机专业知识题库事业单位考试分类

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

自然社会的教育内容之所以不可能在古代社会占主导地位，主要是由于古代社会()。

下列关于性别差异心理的说法，正确的是()。

李老师对学生王大鹏的评语是：“这段时间你开始主动回答老师的课堂提问，学习态度也更加认真。考试时避免了很多不必要的失分，因此你的学习成绩比以前好多了。继续加油，我看好你哦!”这种评价方式是()。

在宏观上，教与学过程是一个系统过程。下列不属于该系统过程要素的是()。

【2012年济宁市市属真题】在教学过程中，素质教育强调的是()，而不是简单地获得结果。

《红楼梦》一书，人物众多，关系复杂，散见于各章，鲁迅先生综合各章信息后，制作了一张主要人物关系表。这种学习策略属于()。

记录讲话时，把可有可无或重复的语句删去，尽可能做到既要注重精，还要注重详，需采用()记录法。

红外无线局域网的数据传输技术不包括以下哪种传输技术?()

简述改革城建税的必要性和原则。

微分方程χy′－y＝0满足条件y｜χ＝1＝2的特解为_______．

对于返工、返修就可以弥补的质量缺陷，监理工程师的处理程序中包括()。

关于概算定额的说法，正确的有()。

完全垄断市场是指在市场上只有一个供给者和众多需求者的市场结构。在我国，下列行业属于完全垄断市场的有()。

某单位今年一月份购买5包A4纸、6包B5纸，购买A4纸的钱比B5纸少5元；第一季度该单位共购买A4纸15包、B5纸12包，共花费510元；那么每包B5纸的价格比A4纸便宜()。

A、Hecan’tcatchupwithhisclassmates.B、HefindstheEnglishcourseloadtooheavy.C、Heisnotinterestedinhispresentmaj