首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。 order (int j,int m) } int i,ternp; if(j<m) { if(a[i]<a[j]) { temp=a [i]; a [j]=temp; } j
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。 order (int j,int m) } int i,ternp; if(j<m) { if(a[i]<a[j]) { temp=a [i]; a [j]=temp; } j
admin
2019-12-10
60
问题
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。
order (int j,int m)
}
int i,ternp;
if(j<m)
{
if(a
<a[j])
{
temp=a
;
a [j]=temp;
}
j++;
order(j,m); //递归调用
}
}
选项
A、O(n)
B、O(nlog
2
n)
C、O(n
2
)
D、O(n
3
)
答案
C
解析
order()函数是一个递归排序过程,设T(n)是排序n个元素所需要的时间。在排序n个元素时,算法的计算时间主要花费在递归调用order()上。第一次调用时,处理的元素序列个数为n—1,也就是对余下的n—1个元素进行排序,所需要的计算时间应为T(n—1)。又因为在其中的循环中,需要n—1次比较,所以排序n个元素所需要的时间为
T(n)=T(n—1)+n—1, n>1
这样得到如下方程:
T(1)=0
T(n)=T(n—1)+n一1 n>1
求解过程为:
T(n)=[T(n一2)+(n一2)]+(n一1)
=[T(n一3)+(n一3)]+(n一2)+(n一1)
.
.
.
=[T(1)+1]+2+…+n—1
=0+1+2+…+n—1
=n(n—1)/2
=O(n
2
)
转载请注明原文地址:https://kaotiyun.com/show/N13i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
某32位计算机系统采用段页式虚拟存储管理,现有一个进程被分成5段,其段号和段长见下表,段内分页,页表见下,存放在内存中,每页的长度为4096B。进程运行到某一个指令,其地址为(2,3,010),当前CPU的寄存器和地址加法器的状态如图所示,当上述指令执行时
用链接方式存储的队列,在进行删除运算时,下面正确的是()。
计算机系统总线包括①地址总线、②数据总线和③控制总线。若采用DMA方式传送数据,需要DMA控制器控制的是()。
循环队列用数组A[0..m~1]存放其元素值,已知其头尾指针分别为front和rear,则当前元素个数为()。
在单处理机的多进程系统中,进程什么时候占用处理机以及决定占用时间的长短是()。
在实现文件系统时,一般为加快文件目录的检索速度,可利用“文件控制块部分装入”的方法。假设目录文件(即文件控制块)存放在磁盘上,磁盘的每个盘块为512B,每个目录项占128B,其中文件名占11B。为提高检索速度,通常将目录项分解成两部分,第一部分(包括文件名
下列关于RISC的叙述中,错误的是____。
下列关于并行微程序控制器的说法正确的是()。
某16位计算机中,带符号整数用补码表示,数据Cache和指令cache分离。题44表给出了指令系统中部分指令格式,其中Rs和Rd表示寄存器,mem表示存储单元地址,(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令,各流水段分别是取指(
随机试题
一新生男婴,于生后3h起反复发生低钙性抽搐,静脉滴注5%.葡萄糖酸钙无效。体检:眼距增宽,小颌畸形,四肢肌张力高。X线胸片未见胸腺影,诊断DiGeorge综合征。可用下列治疗,除了
(事实一)甲是A公司(国有房地产公司)领导,因私人事务欠蔡某600万元。蔡某让甲还钱,甲提议以A公司在售的商品房偿还债务,蔡某同意。甲遂将公司一套价值600万元的商品房过户给蔡某,并在公司财务账目上记下自己欠公司600万元。三个月后,甲将账做平,至案发时亦
连续梁两种受力情况如图所示,力F非常靠近中间铰链。则下面四项中正确结论为( )。
背景资料:某公司承建一项天然气管线工程,全长1380m,公称外径dn110mm,采用聚乙烯燃气管道(SDR11PE100),直埋敷设,热熔连接。工程实施过程中发生了如下事件:事件一:开工前,项目部对现场焊工的执业资格进行检
下列选项中,需要上市公司股东大会行使其特别职权审议批准的有()。Ⅰ.单笔担保额超过最近3期经审计净资产10%的担保Ⅱ.对股东、实际控制人及其关联方提供的担保Ⅲ.公司的对外担保总额达到或超过最近1期经审计总资产的20%以
根据不同的外汇管理制度,汇率可以分为()。
观看乒乓球抽球录像后,能以一定的精确度来演示这一动作的动作技能目标是()。
小刚从A点开始向前走10米,然后向右转60度,他再向前走10米,向右转60度。他继续这样的走法,最后回到A点。问:小刚总共走了多少米?( )
求下列投影点的坐标:(1)点(-1,2,0)在平面x+2y-2+1=0上的投影点;(2)点(2,3,1)在直线上的投影点.
SuggestionsforImprovingReadingSpeedImprovementofReadingRateItissafetosaythatalmostanyonecandoublehisorh
最新回复
(
0
)