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

admin2019-01-16 38

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

“文化大革命”结束后，在纠正“文化大革命”错误的过程中，整个过程受到()的严重阻碍。

简述希波战争过程及其意义。

论述宋初加强中央集权的主要措施。

太平天国时期，提出了一系列向西方学习资本主义方案的重要人物是()。

在下列哪个条约中，最先出现了片面最惠国待遇?()

隋唐科举制的进士科最先出现在()。

美国历史上第一个具有宪法性质的文件是（）。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

IwasonlyeightyearsoldwhentheSecondWorldWarended,butIcanstillremembersomethingaboutthecelebrationsinthesma

腭骨骨折X线检查首选

根据上表数据，可以画出时间与产量关系的散点图为()。根据上述散点图，可以假定骨干线为()。

下列事项中会引起长期股权投资账面价值变动的有()。

汇款人委托银行将款项汇给外地收款人的结算方式是()。

灯杆竖旗的规格一般尺寸为()。

应聘人员选拔的意义包括()。

5753

Pollutionofwatersuppliesisusuallyduetopoorhealthconditionsclosetowatersources,sewage【T1】______intothesourcest