首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
admin
2021-08-17
70
问题
对于一个长度为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
学硕统考专业
相关试题推荐
若某文件系统索引结点(inode)中有直接地址项和间接地址项,则下列选项中,与单个文件长度无关的因素是
用户程序发出磁盘I/O请求后,系统的处理流程是:用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中,计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
某磁盘的转速为10000转/分,平均寻道时间是6ms,磁盘传输速率是20MB/s,磁盘控制器延迟为0.2ms,渎取一个4KB的扇区所需的平均时间约为
在一棵高度为2的5阶B树中,所含关键字的个数最少是
假定某计算机字长16位,没有Cache,运算器一次定点加法时间等于100ns,配置的磁盘旋转速度为每分钟3000转,每个磁道上记录两个数据块,每一块有8000B,两个数据块之间间隙的越过时间为2ms,主存周期为500ns,存储器总线宽度为16位,总线带宽为
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址,虚拟地址16位,物理地址12位,页大小为128B,TLB为4路组相连,共有16个页表项,L1DataCache采用直接映射方式,块大小为4B,共16行。在系统运行到某一
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址,虚拟地址16位,物理地址12位,页大小为128B,TLB为4路组相连,共有16个页表项,L1DataCache采用直接映射方式,块大小为4B,共16行。在系统运行到某一
数据链路层采用后退N帧方式进行流量和差错控制,发送方已经发送了编号0~7的帧。当计时器超时,只收到了对1、3和5号帧的确认,发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习,程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3,要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问:对于(2)简要说明系统是如何使每个学生获得他的程序和数据的?
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I/O设备读取1000B的数据到主存缓冲区中,该I/O设备一旦启动即按50KB/s的数据传输率向主机传送1000B数据,每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期,则以下4种
随机试题
Womenearnlessthanmendo.Forexample,in1998thehourlywagesofwomenintheU.S.were26%lessthanthoseofmen.Thega
患者头晕目花,少气倦怠,腹部有坠胀感,脱肛,舌淡苔白,脉弱。其证候是
长期趋势法多用于比较法中对可比实例价格进行交易日期修正,而不能用来比较、分析两宗(或两类)以上房地产价格的发展趋势或潜力。()
施工合同示范文本通用条款规定,承包人对( )的保修期限为2年。
下列工序中,不属于涂装工艺的是()。
下列不属于担保种类的是()。
每到深秋时节,张老师班上的清洁区总有扫不完的落叶。刚开始很多同学不愿意干活,张老师就带头干。在老师的带动下,班里很多同学都加入了扫树叶的行列,张老师的班级因此经常受到校领导的表扬,同学们也从中体会到了劳动的乐趣。张老师采用的德育方法是(
下列成语中,源于赵匡胤陈桥事变故事的是()。
有一次,苏格拉底淌水过河,脚一划,落水了。他拼命挣扎,大喊救命,不远处有个钓鱼者不但不救他,反而转身就走。最后是他的学生救了他。后来那个钓鱼者淌水过河,也落水了,苏格拉底和他的学生正巧在河边散步,便用竹竿把他救了上来。当学生们知道救上来的就是那个钓鱼者时,
Er______gernSuppevordemHauptgericht.
最新回复
(
0
)