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

admin2013-12-19 30

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

选项

答案假定特排序的记录有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://kaotiyun.com/show/aval777K

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

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

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

计算机专业知识

事业单位考试

提出学习过程应始终以人为本，必须重视学习者的意愿、情感、需要等的学习观是()。

在宏观上，学与教的过程包含的要素有()。

教学的内容、方法、分量和进度要适合学生的身心发展，是他们能够接受的，但又要有一定的难度，需要经过努力才能掌握，以促进学生的身心发展。这说明教学应该遵循()。

中国和西方在词源上赋予教育内涵及形成的教育传统，具有下列哪些区别?()

提出“教学具有教育性原则”的教育家是()。

编码系统和统觉团都属于个体的认知结构。()

学生借助于老师提供的结构图来弄清概念之间的关系。按照奥苏伯尔的学习分类理论，这种学习属于()。

structemployee{longnum；floatsalary；structemployeenext；}；intn；struetemployeedel(struet

下面不是UNIX／Linux操作系统的密码设置原则的是()。

关于过敏性紫癜的实验室检查，错误的是

患者，男，56岁。5年来反复低热、盗汗、消瘦、乏力，X线胸片右上肺有云絮状阴影。最可能是感染了

在一项评价脊髓灰质炎活疫苗效果的研究中，接种疫苗组儿童脊髓灰质炎的发病率是16/10万，接受安慰剂组儿童的发病率是57/10万，疫苗的保护率应该是

入境、出境的微生物、人体组织、生物制品、血液及其制品等特殊物品的携带人、托运人或者邮递人，必须向卫生检疫机关申报并接受卫生检疫。(　　)

在银行代理的信托理财产品中，产品面临的风险主要有()。

鉴定机构进行安全鉴定必须有()鉴定人员参加。

Theprocessbymeansofwhichhumanbeingsarbitrarilymakecertainthingsstandforotherthingsmaybecalledthesymbolicpro

下列属于陈述性知识表征方式的是()

阅读下面程序段：Fora=1To2Forb=1ToaForc=bTo2i=i+1Ne

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

计算机专业知识

事业单位考试

提出学习过程应始终以人为本，必须重视学习者的意愿、情感、需要等的学习观是()。

在宏观上，学与教的过程包含的要素有()。

教学的内容、方法、分量和进度要适合学生的身心发展，是他们能够接受的，但又要有一定的难度，需要经过努力才能掌握，以促进学生的身心发展。这说明教学应该遵循()。

中国和西方在词源上赋予教育内涵及形成的教育传统，具有下列哪些区别?()

提出“教学具有教育性原则”的教育家是()。

编码系统和统觉团都属于个体的认知结构。()

学生借助于老师提供的结构图来弄清概念之间的关系。按照奥苏伯尔的学习分类理论，这种学习属于()。

structemployee{longnum；floatsalary；structemployee*next；}；intn；struetemployee*del(struet

下面不是UNIX／Linux操作系统的密码设置原则的是()。

关于过敏性紫癜的实验室检查，错误的是

患者，男，56岁。5年来反复低热、盗汗、消瘦、乏力，X线胸片右上肺有云絮状阴影。最可能是感染了

在一项评价脊髓灰质炎活疫苗效果的研究中，接种疫苗组儿童脊髓灰质炎的发病率是16/10万，接受安慰剂组儿童的发病率是57/10万，疫苗的保护率应该是

入境、出境的微生物、人体组织、生物制品、血液及其制品等特殊物品的携带人、托运人或者邮递人，必须向卫生检疫机关申报并接受卫生检疫。( )

在银行代理的信托理财产品中，产品面临的风险主要有()。

鉴定机构进行安全鉴定必须有()鉴定人员参加。

Theprocessbymeansofwhichhumanbeingsarbitrarilymakecertainthingsstandforotherthingsmaybecalledthesymbolicpro

下列属于陈述性知识表征方式的是()

阅读下面程序段：Fora=1To2Forb=1ToaForc=bTo2i=i+1Ne

structemployee{longnum；floatsalary；structemployeenext；}；intn；struetemployeedel(struet

入境、出境的微生物、人体组织、生物制品、血液及其制品等特殊物品的携带人、托运人或者邮递人，必须向卫生检疫机关申报并接受卫生检疫。(　　)