首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。 order(int j,int m) { int i,temp; if(j<m) { for(i=j,i<=n;i++) if
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。 order(int j,int m) { int i,temp; if(j<m) { for(i=j,i<=n;i++) if
admin
2014-04-17
76
问题
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。
order(int j,int m)
{
int i,temp;
if(j<m)
{
for(i=j,i<=n;i++)
if(a
<a[j])
{
temp=a
;
a
=a[j];
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/llxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
评介萨缪尔.亨廷顿的“文明冲突论”。(北京大学1996年世界通史真题)
1971年9月美苏英法四国签署(),肯定了西柏林的占领制度,柏林问题得以解决。
斯大林模式的突出特点是()。
南北朝时期,佛教盛行。与此现象无关的是()。
中国共产党在抗日民主根据地实行的土地政策是()。
新王朝时期出现了什么类型的墓?()
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
随机试题
A、Itwillincreasethegovernment’seconomicburden.B、ItwillleadtoapartialshutdownoftheUSgovernment.C、Itwillgiver
车削加工就是在车床上利用工件的旋转运动和刀具的进给运动,加工出各种回转表面、回转体的端面以及螺旋面等。()
A.糖蛋白B.线粒体C.葡萄糖D.果糖成熟红细胞的主要供能物质是
下列情况最容易引起房室传导阻滞的是
男性,58岁,慢性阻塞性肺疾病10余年,近1周咳喘加重,发绀明显,烦躁,血气分析:pH7.39,PaO240mmHg,PaCO270mmHg。如果患者存在呼吸性酸中毒.在治疗中哪项是最根本的措施
以下不属于蛛网膜下腔出血临床表现的是
糖尿病病人应严格限制食用的不包括
根据《企业会计制度》的规定,企业的会计期间包括()。
J.Martin提出的战略数据规划方法的主要内容包括()。
I’llmake______Markwasonceagoodsinger.
最新回复
(
0
)