首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设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
46
问题
设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
学硕统考专业
相关试题推荐
下列口号中不是五四运动期间学生在示威游行时高呼的是()。
两次德国统一的历史条件比较
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
第一次世界大战中的第一次大规模战略决战是()
明长城的起止地点是()。
以下不属于国民党控制金融的“四行”的是()。
蒙古军西征之后,罗斯处于()的控制之下。
1945年,联合国成立之时,创始会员国共有()个国家。
《道威斯计划》的实施所产生的直接结果是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
随机试题
反映企业付款、转账等流动过程的称为_______流,而反映管理方法和请示报告等的称为_____流。
麻疹的出疹在发热后的
工程建设标准批准部门对工程项目执行强制性标准情况进行监督检查的下列内容中,不属于规定内容的是()。
建设项目信息分类和编码体系的统一体现在()。
施工企业委托律师代理诉讼属于()。
“收入-费用=利润”这一会计等式,是复式记账法的理论基础,也是编制资产负债表的依据。()
根据企业所得税法律制度的规定,下列项目中,纳税人在计算应纳税所得额时准予扣除的是()。
根据国际移民组织2003年6月发布的《2003年全球移民报告》,在2003年全球1.75亿国际移民中,约3/5去往发达国家。目前,有5600万移民居住在欧洲,5000万居住在亚洲,居住在北美的有4100万。到2000年底为止,世界上共有难民1600万,其中
在下列经济行为中,属于货币执行流通手段职能的是()。
A、4hours.B、6hours.C、12hours.D、18hours.BW:Whydowehavetofinishthisproposaltonight?It’salready6p.m.Can’twe
最新回复
(
0
)