首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
公务员
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
admin
2013-12-19
34
问题
利用比较的方法进行排序，在最坏情况下，能达到的最好时间复杂度是多少?请给出详细证明。
选项
答案
假定特排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。若二叉树高度是h，则叶子结点个数最多为2
h-1
个；反之，若有u个叶子结点，则二叉树的高度至少有1og
2
u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为1og
2
(n!)的路径，即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)次。根据斯特林公式，有log
2
(n!)=()(nlog
2
n)，即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。
解析
转载请注明原文地址:https://jikaoti.com/ti/U9U3FFFM
本试题收录于：
计算机专业知识题库事业单位考试分类
0
计算机专业知识
事业单位考试
相关试题推荐
课堂教学中最简单和最常用的一种导人方法是()。
提出学习过程应始终以人为本，必须重视学习者的意愿、情感、需要等的学习观是()。
教师课堂教学思想及实施教学过程的基本构想具体体现在()。
下列哪项属于认知的实例?()
沟通教育者、受教育者、教育内容三者的桥梁是()。
下面是一位教师的反思日记。回顾过去，我感觉到，过去一个学期的教学比我前十年的教学总和都更能让我明白什么叫教育。以前，我教过好几个班，并且每班人数都在80左右。每天我的大部分时间都在备课，与学生的交流很少，我只考虑自己能提供什么，很少考虑学生需要什
请从下列选项中选择一种最合理、最合乎逻辑的事件排列顺序。()①在足球及踢足球的人看来，这狂热维持在一个适度的度内是最好的②要狂热的人们去具备理性，基本上是不可能的任务③足球就是这么贱，它一面需要这狂热的球迷，一面又害怕那球迷过于狂热，再抱怨
布鲁纳认为，无论我们选择何种学科，都务必使学生理解该学科的结构，以此建立的课程理论是()。
相对于直线式编排教材，螺旋式编排教材的优点之一是能够将学生的认知结构与学科的逻辑结构相统一。()
【2012年烟台市市直真题】中小学生旷课的，学校应当及时与其父母或其他监护人取得联系。()
随机试题
银盐法测定砷时，为了避免反应过缓或过激，反应温度应控制在()左右。
A．清肝明目B．敛疮生肌C．滋阴润燥D．消肿排脓E．清热利尿芦根具有的功效是
A、3～10gB、1～5gC、1～2gD、0．5～1．5gE、0．1～1．0g沉香具有行气止痛之功，其研末的常用量为
A地甲公司与B地乙公司签订一份书面购销合同，甲公习向乙公司购买冰箱200台，每台价格是1500元。双方约定由乙公司代办托运，甲公司在收到货物后的10日内付款，合同的违约金为合同价款的10％。并且约定了因合同发生纠纷由合同签订地C地的法院管辖。但是，在合同签
下列哪一项不是划分市场类型的依据()。
下列判断正确的是()。
【2014年湖南郴州.判断】社会主义教师职业道德修养的主要内容包括政治业务、心理素质。()
TheoutbreakofswinefluthatwasfirstdetectedinMexicowasdeclaredaglobalepidemiconJune11,2009．Itisthefirstworld
设在采用SQLServer2008数据库的图书馆应用系统中有三个基本表，表结构如下所示，请用SQL语句完成下列两个查询：BORROWER：借书证号姓名系名班级12011106蒋辉文
SpringhascometoPortlandatlast.Theskyisblue.Birds【M1】______aresingingonthetrees,flowersareblooming,and
最新回复
(
0
)
