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

admin2017-11-14 90

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

选项

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

学硕统考专业

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

清末新政未能挽救清朝灭亡命运的根本原因是()

苏联解体、东欧剧变的根本相同原因是()。

义和团爆发的直接原因是()。

埃及曾两次被波斯帝国征服，波斯第二次征服埃及的时间是()。

西汉末年，将《太初历》调整为《三统历》的是()。

唐朝官营手工业中，每年服役二十天，在政府“趋役不尽及别有和雇”的情况下，可“纳资代役”的是()。

下列不属于延安整风运动的文件是()。

下列几种排序方法中，要求内存量最大的是()。

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

行政组织编制总体设计的依据是()

鉴别腹股沟斜疝与直疝最有价值的临床表现是

确诊慢性胃炎最可靠的检查方法

对流动人口中的传染性非典型肺炎病人、疑似病人处理的原则是

对于河流完全混合模式，影响污染物最终浓度的因素包括()。

海关对外商投资企业签发的“进出口货物征免税证明”是按()签发的。

在网络图中，计算时间值的目的包括()。

关于书刊装帧加工的说法，正确的是()。

设袋中有5个球，其中3个新球，2个旧球，从中任取3个球，用X表示3个球中的新球个数，求X的分布律与分布函数．

Parentswhosmokeoftenopenawindoworturnonafantocleartheairfortheirchildren,butexpertsnowhaveidentifiedar