首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设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
43
问题
设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
学硕统考专业
相关试题推荐
“瓜步之战”发生在下列哪两个政权之间?()
戊戌政变发生的时间是()。
日本在《二十一条》中提出:“中国沿海岛屿不得租于他国。”其真实目的是()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
欧洲历史上第一部系统完备的法典是()。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为带书。④马钧发明翻车
格拉古兄弟改革的内容和结果是什么?
中国共产党召开七届二中全会的主要目的是()。
通过改变载波信号的相位值来表示数字信号1、0的方法是()。
进程P0和P1的共享变量定义及其初值为:booleanflag[2]:intturn=0:flag[0]=FALSE;flag[1]=FALSE;若进程P0和P1访问临界资源的类C伪代码实现如下:则并发执行进程P0和P1时产生的情形是____。
随机试题
焊工在更换焊条时,可以赤手操作。()
氯霉素的不良反应中,哪种与抑制蛋白的合成有关
决定商业项目功能定位的主要因素是()。
为承办每年全省高校运动会,某高校新建一栋体育馆,由主体建筑和附属建筑两部分组成。主体建筑为比赛馆,附属建筑为训练馆,建筑高度为23m,总建筑面积为1.70万m2,采用框架及大跨度钢屋架结构体系,耐火等级二级。比赛馆为单层大空间建筑,可容纳观众席4446个,
下面是关于美国联邦储备委员会2003年降低美元利率的材料:美联储决策者今天把主要的美元利率降低了0,25个百分点,降至1%,为45年来最低的水平。这是为了避免出现通货紧缩而采取的防范措施。美联储主席格林斯潘及其同事把联邦基金的目标利率—
分布于不同地方的语言使用者,在长期的发展过程中,积累了生产生活的共同或独特的经验。这些经验或知识体系都凝聚在语言之中,而各个语言群体对自然界的认识分别在不同的方面达到了不同的深度,形成了认识结构的互补分布,共同构成了人类广博精深的知识体系。这段文字意在说明
设有变量sr=“2000年上半年全国计算机等级考试”,能够显示“2000年上半年计算机等级考试”的命令是______。
ModifyCommand命令建立的文件的默认扩展名是()。
在工作日而不是周末出行,会节省不少费用。(ratherthan)
Almost20,000whaleshavebeenslaughteredsincea【B1】______oncommercialwhalingwasintroducedin1986andthedeath【B2】______
最新回复
(
0
)