首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设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
51
问题
设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
学硕统考专业
相关试题推荐
在操作系统层次结构中,()是操作系统的核心部分,它位于最内层。
假定某采用页式虚拟存储管理的计算机系统中,主存储器容量为1GB,被分为262144块物理块,物理块号为0,1,2,……,262143。某进程的地址空间占4页,逻辑页号为0,1,2,3,被分配到主存储器的第20,45,101,58号物理块中。回答:
一个磁盘有N个磁道,寻道时每移过一个磁道耗时T秒,文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道,磁盘旋转延时平均R秒,每个存储块的传输时间为P秒,在这种情况下,传输100个数据块需要的时间是()。
下面关于图的存储的叙述中,正确的是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
数据链路层采用选择重传协议(SR)传输数据,发送方已发送了0~3号数据帧,现已收到1号帧的确认,而0、2号帧依次超时,则此时需要重传的帧数是____。
假设某系统总线在一个总线周期中并行传输4B信息,一个总线周期占用2个时钟周期,总线时钟频率为10MHz,则总线带宽是____。
在补码表示的机器中,若寄存器A中原存的数为9EH,现存的数为CFH,则表明执行的一条指令是()。
设无向图G=(V,E)和G’=(V’,E’),如果G’是G的生成树,则下面说法中错误的是()。
下列说法中不正确的是()。
随机试题
A、AttendingDr.Alberti’slecture.B、Sharingone’sfeelingswithothers.C、Talkingwithasuperior.D、Chattingwithotherpeople
公民、法人或者其他组织认为具体行政行为侵犯其合法权益的,可以自知道该具体行政行为之日起()内提起行政复议的申请。
∫01(x2-2x)dx=().
下列关于地下防水施工的叙述错误的是()。
将自产、委托加工或购买的货物用于非应税项目属于视同销售货物。()
某个村子有个有趣的习俗:村子里所有80岁以上的人都必须说假话,80岁以下的人都必须说真话。你进到村子的时候,看到村子中所有的人围坐一圈,每个男人的两边都是女人,每个女人的两边都是男人。你问一个名为古瓦哈提的村民:你们村子有多少人?古瓦哈
我国历代思想家、教育家有关师德修养的内容有()。
正当防卫:是指为了使国家、公共利益、本人或者他人的人身、财产和其他权利免受正在进行的不法侵害,而采取的制止不法侵害的行为。根据上述定义,下列哪一个属于正当防卫:
设三阶矩阵A的特征值为-1,1,2,其对应的特征向量为α1,α2,α3,令P=(3α2,-α3,2α1),则P-1AP等于().
一般采用________________语言编写.NET项目的配置文件。
最新回复
(
0
)