首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
32
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2
h-1
；反之，若有u个叶子结点，则二叉树的高度至少为(log
2
u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log
2
(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log
2
(n!)。根据斯特林公式，有log
2
(n!)=O(nlog
2
n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog
2
n)。
解析
转载请注明原文地址:https://jikaoti.com/ti/23fjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
改革开放以后，我国农村产业结构巨大的转变表现在()。
关于1957年的整风运动，下列不属于其内容的是()。
简述格拉古兄弟改革的主要内容和历史意义。
阅读材料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合理解决，
两汉时期，下列没有通过丝绸之路传入西方的技术是()。
印加人记载事物使用的方法是()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
商朝号称青铜时代，下列叙述不符合当时的历史情况的是()
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
随机试题
tRNA的功能
增殖型肠结核X线征象中不包括
以下项目中不是财产清查的基本程序的有()。
人员的()是招聘过程中最关键的一步，也是技术性最强、难度最大的一步。
为什么要挽救濒临灭绝的物种呢?对公众来说，濒危动物与生物学上的奇异行为差不多。从更广的范围内考虑物种灭绝的问题，便得出了另一个不同的观点，其要点为：很多重要的社会进步都是以生命形式为基础的，而这些形式的价值不可能预先被感知，看看产橡胶的植物对当代生活和工业
享有外交特权和豁免权的外国人在我国领域内犯罪的，()。
某二叉树共有7个结点，其中叶子结点只有1个，则该二叉的深度为(假设根结点在第1层)
•Lookatthenotesbelow.•Someinformationismissing.•Youwillhearpartofatalkgiventoagroupofnewempolyees.•Fo
Theestimatesofthenumbersofhome-schooledchildrenvarywidely.TheU.S.DepartmentofEducationestimatesthereare250,00
PreparingChildrentoBeSafeatCollegeA)Moneycanbuymanythingstohelpchildrenexcelacademically,liketutorsandprivat
最新回复
(
0
)
