首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
admin
2019-01-16
69
问题
利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
选项
答案
假定待排序的记录有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://kaotiyun.com/show/glRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
科学技术革命包括三个既有联系又有区别的过程，下列不属于三个过程的是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的，密谋发动()。
美国历史上第一个具有宪法性质的文件是（）。
试述西欧城市兴起的原因、方式及其影响。
下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
到1869年为止，人类已发现了多少种化学元素()。
阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
设某多道程序系统中有用户使用内存1000M，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算法，进程调度时机选择在进程执行结
随机试题
喉癌可分成声门上型，声门型，声门下型和跨声门型，其中声门下型约站喉癌病例的
A．芦根B．淡竹叶C．天花粉D．栀子E．夏枯草
关于记账操作，下列说法中错误的是（ ）。
关于短期总成本曲线的说法，正确的是()。
食品安全管理制度包括()
清朝最重要的会审制度是()。
[*]
Ashumanchildrenareunusuallydependentfaranunusuallylongtime,it’sobviousthateverysocietymustprovideadomesticco
有指令MOV AX，COUNT[SI]，如果(DS)=3000H，(SI)=2000H，COUNT=3000H，则物理地址是( )
下面关于随机存取存储器(RAM)的叙述中，正确的是
最新回复
(
0
)
