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

admin2013-12-19 72

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

选项

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

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

计算机专业知识

事业单位考试

“以身立教”“为人师表”体现了教师劳动的()特点。

奴隶社会学校教育的内容是礼、乐、射、御、书、数，世称()。

教育发展受制于政治经济制度等因素，但也具有相对独立性，具体表现在()。

将教学过程作为一个“输入——产出”的系统过程，属于教学设计的()。

下列表述中，与“盈科而后进”所体现的教学原则相一致的是()。

处于具体运算阶段的儿童()。

计算机辅助教学中的教学模式是()的有机结合，是为完成现代教学与学习任务采用的相对稳定的，用以设计、组织、实施、评估、优化教学与学校的策略方法和结构的简化形式。

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

在C语言中，标识符只能由字母、文字和下画线三种字母组成，并且第一个字母必须是字母。()

间隙配合的特征是孔的公差带在轴的公差带之下。(

某疑似肺血栓栓塞症病人，右下肢疼痛或压痛、浅静脉扩张、皮肤色素沉着、行走后患肢易疲劳或肿胀加重。下肢周径的测量点为

作为综合评价判据的单一指标,应设置为()。

某工地装修采用的大量安装在金属龙骨上燃烧性能达到B1级的矿棉吸声板，可作为()级装修材料使用。

下列各项中可以作为记账依据的会计凭证是(　　)。

投保人变更受益人未通知保险人，保险人主张变更对其不发生效力的，人民法院应予支持()。

税收保全措施适用于()。

Despitethefactthattodayvirusesareknowntocausecancerinanimalsandincertainplants,whereexistsagreatreluctance

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

计算机专业知识

事业单位考试

“以身立教”“为人师表”体现了教师劳动的()特点。

奴隶社会学校教育的内容是礼、乐、射、御、书、数，世称()。

教育发展受制于政治经济制度等因素，但也具有相对独立性，具体表现在()。

将教学过程作为一个“输入——产出”的系统过程，属于教学设计的()。

下列表述中，与“盈科而后进”所体现的教学原则相一致的是()。

处于具体运算阶段的儿童()。

计算机辅助教学中的教学模式是()的有机结合，是为完成现代教学与学习任务采用的相对稳定的，用以设计、组织、实施、评估、优化教学与学校的策略方法和结构的简化形式。

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

在C语言中，标识符只能由字母、文字和下画线三种字母组成，并且第一个字母必须是字母。()

间隙配合的特征是孔的公差带在轴的公差带之下。(

某疑似肺血栓栓塞症病人，右下肢疼痛或压痛、浅静脉扩张、皮肤色素沉着、行走后患肢易疲劳或肿胀加重。下肢周径的测量点为

作为综合评价判据的单一指标,应设置为()。

某工地装修采用的大量安装在金属龙骨上燃烧性能达到B1级的矿棉吸声板，可作为()级装修材料使用。

下列各项中可以作为记账依据的会计凭证是( )。

投保人变更受益人未通知保险人，保险人主张变更对其不发生效力的，人民法院应予支持()。

税收保全措施适用于()。

Despitethefactthattodayvirusesareknowntocausecancerinanimalsandincertainplants,whereexistsagreatreluctance

下列各项中可以作为记账依据的会计凭证是(　　)。