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

admin2013-12-19 38

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

选项

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

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

计算机专业知识

事业单位考试

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

下列选项表述正确的是()。

相对于直线式编排教材，螺旋式编排教材的优点之一是能够将学生的认知结构与学科的逻辑结构相统一。()

按照皮亚杰的认知发展阶段理论，思维发展处于前运算阶段的个体的思维特点有()。

根据《服务贸易总协定》的规定，属于我国政府承诺的教育贸易服务范畴的是()。

【2015年济南市真题】将一门学科的内容按照逻辑体系组织起来，前后内容基本不重复。体现的课程组织形式是()。

操作系统对设备尽量提供各种不同的接口。()

简述对称密钥密码体制、非对称密钥密码体制的加密原理和各自的特点。

结核性脑膜炎的脑脊液特点为

某单位组织员工体检，某员工的检验结果显示乙肝五项中仅抗—HBs阳性。其余均为阴性，肝功能正常，该员工咨询阳性结果的意义，护士应告知其抗—HBs阳性是表明()

手工铺砂法测试路面构造深度的注意事项有()。

某黄酒厂(增值税一般纳税人)将2吨自产黄酒发放给职工作福利，其成本4000元／吨，成本利润率10％，每吨消费税税额240元，计算该酒厂此项业务应缴纳的消费税和增值税销项税额。

苏州四大历史名园是()

社会主义时期我国民族关系呈现出的发展趋向是(　)。

[*]

为了避免第三方偷看www浏览器与服务器交互的敏感信息，通常需要()。

Nearlyeverybodyenjoyschicken,andthemostfamousnameinchickenisKentuckyFriedChickenMr.Sanders,themanwhostarted

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

计算机专业知识

事业单位考试

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

下列选项表述正确的是()。

相对于直线式编排教材，螺旋式编排教材的优点之一是能够将学生的认知结构与学科的逻辑结构相统一。()

按照皮亚杰的认知发展阶段理论，思维发展处于前运算阶段的个体的思维特点有()。

根据《服务贸易总协定》的规定，属于我国政府承诺的教育贸易服务范畴的是()。

【2015年济南市真题】将一门学科的内容按照逻辑体系组织起来，前后内容基本不重复。体现的课程组织形式是()。

操作系统对设备尽量提供各种不同的接口。()

简述对称密钥密码体制、非对称密钥密码体制的加密原理和各自的特点。

结核性脑膜炎的脑脊液特点为

某单位组织员工体检，某员工的检验结果显示乙肝五项中仅抗—HBs阳性。其余均为阴性，肝功能正常，该员工咨询阳性结果的意义，护士应告知其抗—HBs阳性是表明()

手工铺砂法测试路面构造深度的注意事项有()。

某黄酒厂(增值税一般纳税人)将2吨自产黄酒发放给职工作福利，其成本4000元／吨，成本利润率10％，每吨消费税税额240元，计算该酒厂此项业务应缴纳的消费税和增值税销项税额。

苏州四大历史名园是()

社会主义时期我国民族关系呈现出的发展趋向是( )。

[*]

为了避免第三方偷看www浏览器与服务器交互的敏感信息，通常需要()。

Nearlyeverybodyenjoyschicken,andthemostfamousnameinchickenisKentuckyFriedChickenMr.Sanders,themanwhostarted

社会主义时期我国民族关系呈现出的发展趋向是(　)。