首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设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
70
问题
设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年世界通史真题)
我国第一部系统的史学理论著作是()。
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
清朝,各地督抚将重大问题径寄军机处交皇帝审批,称为()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
随机试题
关于肾盂积水,下列哪项描述正确
患者,女,28岁。妊娠38周,患心脏病。刚临产,产科情况暂无异常。心功能Ⅱ级。在宫口接近开全时,心功能仍为Ⅱ级,首先要做好的是
膀胱癌的血尿特点是
A.可可豆脂B.十二烷基硫酸钠C.卡波姆D.羊毛脂E.丙二醇常作栓剂基质的是()
男婴,1岁半。发热4天,伴咳嗽,流涕,眼结膜充血,流泪,半天前发现患儿耳后、颈部、发缘有稀疏的不规则红色丘斑疹,疹间皮肤正常,体温40℃,心肺正常。护士指导家长患儿应隔离至出疹后
地A公司和乙地B公司在丙地签订一份买卖合同,约定由B公司在丁地向A公司交货。后B公司未能按约履行合同,A公司便向人民法院提起诉讼。根据规定,该案有管辖权的人民法院是( )。
某运输企业,2011年12月成立,2012年度相关生产经营业务如下:(1)当年公路运输收入700万元,国债利息收入10万元、取得对境内非上市公司的权益性投资收益46.8万元。(2)全年营业成本为320万元;营业税金及附加23.1万元。
有一个数值311与十六进制数C9相等,则该数值是()数。
设f(χ)=χsinχ-∫0χ(χ-t)f(t)dt,其中f(χ)连续,求f(χ).
Youarerequiredtowriteanessayoffthetopic"StressinModemLife".Youshouldwritenolessthan200wordsneatly,and
最新回复
(
0
)