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

admin2013-12-19 56

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

选项

答案假定特排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。若二叉树高度是h，则叶子结点个数最多为2^h-1个；反之，若有u个叶子结点，则二叉树的高度至少有1og₂u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为1og₂(n!)的路径，即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)次。根据斯特林公式，有log₂(n!)=()(nlog₂n)，即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog₂n)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/aval777K

本试题收录于：计算机专业知识题库事业单位考试分类

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

张宏在听课时经常将学习内容要点以画线的方式在书上做标记，这种学习策略属于()

周围神经系统由()组成。

在对事物的知觉中，需要有以往经验、知识为基础的理解，以便对知觉的对象做出最佳解释，说明知觉的这一特性叫()。

根据课程计划以纲要形式编订的有关学科教学内容的目的、水准、结构与教学要求的纲领性文件是()。

两位老师对学生进行英语学习的元认知策略训练，两人共同讨论、评课、写教案，请问两位老师采用的研究方法是()。

在Windows系统中，若强行关闭一个正在运行的程序，可以使用任务管理器来结束它。打开任务管理器需按下()。

在德育历史发展过程中，其原理、原则和内容、方法等存在一定的共同性，因此，德育具有()。

在端到端之间提供可靠数据传输的是计算机网络体系结构中的()。

红外无线局域网的数据传输技术不包括以下哪种传输技术?()

简述预算编制和执行中的局限性。

A、还少丹B、洗心汤C、七福饮D、导痰汤E、温胆汤治疗帕金森病风痰阻络证，宜选

建设行政主管部门监督招标投标活动的工作人员可以(　　)。

()是国家宏观经济政策的制定者，是一国证券市场上有关信息的主要来源。

解决问题的基本过程是()。

左边给定的是纸盒的外表面，下面哪一项能由它折叠而成?

20，42，72，110，()。

Energywillbeoneofthedefiningissuesofthiscentury.Onethingisclear:theeraof(1)_____oilisover.Whatwealldon

若有定义语句：intm[]={5，4，3，2，1}，i=4；，则下面对m数组元素的引用中错误的是()。

A、It’ssummervacation.B、It’stooold.C、It’stooexpensive.D、Theyliveinthedorm.A题目问Laura为什么觉得学生不会买家具。对话中Laura建议David对于家具

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

计算机专业知识

事业单位考试

张宏在听课时经常将学习内容要点以画线的方式在书上做标记，这种学习策略属于()

周围神经系统由()组成。

在对事物的知觉中，需要有以往经验、知识为基础的理解，以便对知觉的对象做出最佳解释，说明知觉的这一特性叫()。

根据课程计划以纲要形式编订的有关学科教学内容的目的、水准、结构与教学要求的纲领性文件是()。

两位老师对学生进行英语学习的元认知策略训练，两人共同讨论、评课、写教案，请问两位老师采用的研究方法是()。

在Windows系统中，若强行关闭一个正在运行的程序，可以使用任务管理器来结束它。打开任务管理器需按下()。

在德育历史发展过程中，其原理、原则和内容、方法等存在一定的共同性，因此，德育具有()。

在端到端之间提供可靠数据传输的是计算机网络体系结构中的()。

红外无线局域网的数据传输技术不包括以下哪种传输技术?()

简述预算编制和执行中的局限性。

A、还少丹B、洗心汤C、七福饮D、导痰汤E、温胆汤治疗帕金森病风痰阻络证，宜选

建设行政主管部门监督招标投标活动的工作人员可以( )。

()是国家宏观经济政策的制定者，是一国证券市场上有关信息的主要来源。

解决问题的基本过程是()。

左边给定的是纸盒的外表面，下面哪一项能由它折叠而成?

20，42，72，110，()。

Energywillbeoneofthedefiningissuesofthiscentury.Onethingisclear:theeraof(1)_____oilisover.Whatwealldon

若有定义语句：intm[]={5，4，3，2，1}，i=4；，则下面对m数组元素的引用中错误的是()。

A、It’ssummervacation.B、It’stooold.C、It’stooexpensive.D、Theyliveinthedorm.A题目问Laura为什么觉得学生不会买家具。对话中Laura建议David对于家具

建设行政主管部门监督招标投标活动的工作人员可以(　　)。