首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是( )。
admin
2021-08-17
72
问题
对于一个长度为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请求后,系统的处理流程是:用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中,计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
一个栈的入栈序列为1,2,3,…,n,其出栈序列是ρ1,ρ2,ρ3,…,ρn。若p2=3,则ρ可能取值的个数是
假定某计算机字长16位,没有Cache,运算器一次定点加法时间等于100ns,配置的磁盘旋转速度为每分钟3000转,每个磁道上记录两个数据块,每一块有8000B,两个数据块之间间隙的越过时间为2ms,主存周期为500ns,存储器总线宽度为16位,总线带宽为
有某个操作系统对外存分配采用混合索引分配方式。在索引节点中包含了文件的物理结构数组iaddr[12],其中前10项iaddr[O]~iaddr[9]为直接地址,iaddr[10]为一次间接地址,iaddr[11]为二次间接地址。如果系统的块的大小是4KB,
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址,虚拟地址16位,物理地址12位,页大小为128B,TLB为4路组相连,共有16个页表项,L1DataCache采用直接映射方式,块大小为4B,共16行。在系统运行到某一
现有一种解决无向连通图的最小生成树的方法:将图中所有边按权重从大到小排序为(e1,e2,…,em);i=1;while(所剩边数≥顶点数){从图中删去ei;若图不再连通,则恢复ei;i++;
数据链路层采用后退N帧方式进行流量和差错控制,发送方已经发送了编号0~7的帧。当计时器超时,只收到了对1、3和5号帧的确认,发送方需要重传的帧的数目是()。
现有3名学生S1、S2和S3上机实习,程序和数据都存放在同一磁盘上。若3人编写的程序分别为P1、P2和P3,要求这3个学生用自编的程序调用同一个数据文件A进行计算。试问:若文件A作为共享文件,系统应采用何种目录结构?画出示意图。
随机试题
血管紧张素转化酶抑制剂不适用于
桥孔溢流水力计算是基于什么堰流:
下列工程中,不属于机电工程专业建造师执业范围的是()工程。
构件按最小配筋率配筋时,按()原则代换钢筋。
2×17年12月,经董事会批准,甲公司自2×18年1月1日起撤销某营销网点,该业务重组计划已对外公告。为实施该业务重组计划,甲公司预计发生以下支出或损失:因辞退职工将支付补偿款100万元,因撤销门店租赁合同将支付违约金20万元,因处置门店内设备将发生损失5
下列()行为,属于违反《风景名胜区管理暂行条例》。
劳务派遣单位的职责包括()。
科举考试的殿试始于()。
A、 B、 C、 D、 A
After21yearsofmarriage,mywifewantedmetotakeanotherwomanouttodinnerandamovie.Shesaid,"Iloveyou,butIknow
最新回复
(
0
)