首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设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
35
问题
设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
学硕统考专业
相关试题推荐
简述近代香港问题的形成。
玛雅人的金字塔主要功能是()。
下列著作不属于被后世称为清代汉学的“不祧祖先”之人的作品的是()
西汉时期,张骞第一次出使西域的主要目的是()
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
简述弭兵之会的背景、过程和结果。
1895年发现X射线,拉开物理学革命序幕的科学家是()。
西汉初年,西域共有36国,其中以()人口最多。
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
随机试题
A.花椒B.藏红花C.细辛D.泽泻E.牡丹皮可与蕲蛇同贮的是()。
呼吸机辅助呼吸的目的不包括
刘某将自己的电脑交赵某保管,后赵某将该电脑非法占为已有,拒不退还刘某,刘某多次索要无果后因病去世。刘某之女以侵占罪向人民法院提交了刑事自诉状。代其父亲控告赵某。对于刘女这种代其父亲告诉的情况,人民法院不正确的做法是?
水利工程建设项目的质量监督期为()。
组合管理者在强式有效市场中选择消极保守型投资。()
在处理游客死亡事故时,必须有死者的亲属、领队、使馆人员及旅行社有关领导在场。()
价值规律的作用是()。
2010年,全国国有建没用地土地供应总量42.8万公顷,比上年增长18.4%。其中,工矿仓储用地15.3万公顷,增长7.9%;商服用地3.9万公顷,增长40.4%;住宅用地11.4万公顷,增长40.3%;基础设施等其他用地12.2万公顷,增长10.2%。全
某公司董事长孙某当选为区人大代表。下列关于孙某履行义务的说法,正确的是()。
患者,男性,76岁,无牙颌,要求全口义齿修复。既往曾多次要求全口义齿修复,均不适。检查发现:下颌牙槽嵴极度低平,上颌牙弓窄于下颌牙弓,舌体增大,黏膜薄,下颌呈习惯性前伸,张口不受限,旧义齿固位差,关系不稳定。为了减轻34所受的扭力,可以采取以下措施,除了(
最新回复
(
0
)