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

admin2019-08-01 67

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

罗斯福新政策称为是“3R”改革即Recovery(复兴)、Relief(救济)、Reform(改革)，其中能反映Relief方面的内容是()。

胡适与李大钊“问题与主义”论战主要的阵地是()。

1141年，金与南宋双方签订协议，规定以淮水和大散关为宋金的分界线，此协议称为（）。

新文化运动前期的指导思想是()。

对三国鼎立局面的形成起到关键性作用的战役是()。

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

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

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

韦伯指出，世袭的统治者很大程度依赖于他的臣民的

简述艺术活动的构成。

根据《建设工程项目管理规范》，项目风险管理正确的程序是()。

运营活动，是指投入一定的资源，经过一系列多种形式的变换，使其价值增值，最后以某种形式的产出提供给社会的过程。根据上述定义，下列选项不属于运营活动的是()。

一个好的学者，要么具有很好的学术天赋，要么是经过了长期不懈的后天努力。金灵先生终身致力于学术研究，那么(　)。

Mr.Wrightwasthe______presidentofAceConstructionCompany.

WhenRodLavergotbehind,hewould

WhichofthefollowingdetailsinthenewsisCORRECT?

Kathywasauniversitystudent.Likemoststudentsshehadverylittlemoney,butshewantedtobuyacar."IfIcanbuyon

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

计算机408

学硕统考专业

罗斯福新政策称为是“3R”改革即Recovery(复兴)、Relief(救济)、Reform(改革)，其中能反映Relief方面的内容是()。

胡适与李大钊“问题与主义”论战主要的阵地是()。

1141年，金与南宋双方签订协议，规定以淮水和大散关为宋金的分界线，此协议称为（）。

新文化运动前期的指导思想是()。

对三国鼎立局面的形成起到关键性作用的战役是()。

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

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

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

韦伯指出，世袭的统治者很大程度依赖于他的臣民的

简述艺术活动的构成。

根据《建设工程项目管理规范》，项目风险管理正确的程序是()。

运营活动，是指投入一定的资源，经过一系列多种形式的变换，使其价值增值，最后以某种形式的产出提供给社会的过程。根据上述定义，下列选项不属于运营活动的是()。

一个好的学者，要么具有很好的学术天赋，要么是经过了长期不懈的后天努力。金灵先生终身致力于学术研究，那么( )。

Mr.Wrightwasthe______presidentofAceConstructionCompany.

WhenRodLavergotbehind,hewould

WhichofthefollowingdetailsinthenewsisCORRECT?

Kathywasauniversitystudent.Likemoststudentsshehadverylittlemoney,butshewantedtobuyacar."IfIcanbuyon

一个好的学者，要么具有很好的学术天赋，要么是经过了长期不懈的后天努力。金灵先生终身致力于学术研究，那么(　)。