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

admin2017-11-14 54

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

【朱熹】山西大学2012年中国古代史复试真题；西北大学2013年专门史真题；南开大学2014年日本史真题

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

“国际工人协会”宣布成立后，10月协会选出了第一任主席，他是()。

克里特文明的文字类型是()。

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

詹天佑自主设计修建了中国第一条铁路是在()。

以海地和巴西为例，论述19世纪拉丁美洲民族独立运动类型多样化的历史依据。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

在散列表中，当装填因子非常接近1时，线性探测类似于()查找。

下列关于G蛋白的叙述，错误的是

患者，男，46岁。腹痛腹泻2天，日泻10余次水便，经治已缓，目前口渴心烦，皮肤干瘪，眼窝凹陷，舌淡白苔薄黄，脉细无力。其证候是()

关于非法吸收公众存款罪，下列说法正确的是：()

对房地产经纪信息的鉴别，就是对房地产经纪信息的()等进行分析。

[1999年第139题]按《住宅设计规范》规定，下列各部位门洞口的最小尺寸哪一条不正确?

4Ps营销策略包括()。

车轮(压制钢车轮)(汽油发动机小轿车专用)

决定商品流通中货币需要量的因素有()。

根据下列资料，回答问题。2015年A区域粮食总产量58957万吨，比上年增加1836万吨，增长3．2％，其中，夏粮产量12995万吨，比上年增长2．8％；早稻产量3329万吨，增长1．6％；秋粮产量42633万吨，增长3．5％。2015年末，该区

ReligiousceremoniesAwereperformedtomarkimportantBstagesoflife(births,marriages,deaths)andCtoaskthespiritsforhel