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

admin2017-11-14 77

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

选项

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

学硕统考专业

中国第一个资产阶级革命团体兴中会建立的时间是()。

下列不属于战时共产主义政策内容的是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

下面关于新经济政策的说法不正确的一项是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

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

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是____。

In2013,NewYorkStateorderedstorestochargeadepositonbeverage(饮料)containers.Withinayear,consumershadreturnedmil

颞叶底部血肿，出血动脉是

下列不属于药剂学的任务是

下列关于股份有限公司责任的说法中，正确的有()。Ⅰ．股东以自身财产对公司债务承担责任Ⅱ．公司以全部财产对公司债务承担责任Ⅲ．股东以认购股份对公司债务承担责任Ⅳ．公司以未分配利润对公司债务承担责任

学校是学生心理健康的主要场所。()

Susan:I’msogladtoseeyou,David.【K1】______hasbeensuchalongtime.Howareyou?David:I’mfine,andyou?Susan:I’mjus

1　　Thereisanacceleratingtrendtowardgreaterrealisminmediacommunications.Thistrendcanbeattributedtotechnological

Thisisratherforyourmothertodecidethanforyou．

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

计算机408

学硕统考专业

中国第一个资产阶级革命团体兴中会建立的时间是()。

下列不属于战时共产主义政策内容的是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

下面关于新经济政策的说法不正确的一项是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

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

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是____。

In2013,NewYorkStateorderedstorestochargeadepositonbeverage(饮料)containers.Withinayear,consumershadreturnedmil

颞叶底部血肿，出血动脉是

下列不属于药剂学的任务是

下列关于股份有限公司责任的说法中，正确的有()。Ⅰ．股东以自身财产对公司债务承担责任Ⅱ．公司以全部财产对公司债务承担责任Ⅲ．股东以认购股份对公司债务承担责任Ⅳ．公司以未分配利润对公司债务承担责任

学校是学生心理健康的主要场所。()

Susan:I’msogladtoseeyou,David.【K1】______hasbeensuchalongtime.Howareyou?David:I’mfine,andyou?Susan:I’mjus

1 Thereisanacceleratingtrendtowardgreaterrealisminmediacommunications.Thistrendcanbeattributedtotechnological

Thisisratherforyourmothertodecidethanforyou．

1　　Thereisanacceleratingtrendtowardgreaterrealisminmediacommunications.Thistrendcanbeattributedtotechnological