首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
admin
2021-08-17
71
问题
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
选项
A、O(n)
B、O(n
2
)
C、O(log
D、O(nlogn)
答案
D
解析
在排序过程中,每次比较会有两种情况出现,若整个排序过程中至少需要t次比较,则显然会有2
t
种情况,由于n个记录总共有n!种不同的排列,因而必须有n!种不同的比较路径,于是有:2
t
≥n!,即t≥log
2
(n!)。因为log
2
(n!)≈nlog
2
n,所以t≥nlog2n。
转载请注明原文地址:https://www.kaotiyun.com/show/HD3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于中断I/O方式和DMA方式比较的叙述中,错误的是
用海明码对长度为8位的数据进行检/纠错时,若能纠正一位错,则校验位数至少为
若对如下无向图进行遍历,则下列选项中,不是广度优先遍历序列的是
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址,虚拟地址16位,物理地址12位,页大小为128B,TLB为4路组相连,共有16个页表项,L1DataCache采用直接映射方式,块大小为4B,共16行。在系统运行到某一
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
数据链路层采用后退N帧方式进行流量和差错控制,发送方已经发送了编号0~7的帧。当计时器超时,只收到了对1、3和5号帧的确认,发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习,程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3,要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问:对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?
现有3名学生S1、S2和S3上机实习,程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3,要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问:若文件A作为共享文件,系统应采用何种目录结构?画出示意图。
假定磁盘传输数据以32bit的字为单位,传输速率为1MB/s。CPU的时钟频率为50MHz。采用DMA控制进行输入输出操作,假定DMA的启动操作需要1000个时钟周期,DMA完成时处理中断需要500个时钟周期,如果平均传输的数据长度为4KB,问在磁盘工
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I/O设备读取1000B的数据到主存缓冲区中,该I/O设备一旦启动即按50KB/s的数据传输率向主机传送1000B数据,每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期,则以下4种
随机试题
睾丸病理改变的TM1分类法中,以下哪项不是生精小管的观察指标?
将活塞环放在环槽内,围绕环槽滚动一圈,环在槽内应滚动自如,既不松动,又无阻滞现象。()
A.灵芝B.朱砂C.琥珀D.远志有补气安神功效的药物是
二尖瓣狭窄肥厚型梗阻性心肌病
A.沉而有力B.数而无力C.数而有力D.浮而无力E.迟而有力小儿实热证的脉象是
尿路感染最常见的致病菌是()。
秘书在选择办公用品供应商时应注意其可靠性,包括对()的考虑。
下列关于初级市场与二级市场关系的论述正确的是()。
SpareaKidney?Itisnolongerunusualforaspouseorrelativetodonateakidneytoalovedone,butthenumberofAmerica
A、Shedoesn’tlikeanenergetictype.B、Shedoesn’tlikeaquiettype.C、Shedoesn’tlikeahumoroustype.D、Shedoesn’tlikea
最新回复
(
0
)