首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。 order (int j,int m) } int i,ternp; if(j<m) { if(a[i]<a[j]) { temp=a [i]; a [j]=temp; } j
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。 order (int j,int m) } int i,ternp; if(j<m) { if(a[i]<a[j]) { temp=a [i]; a [j]=temp; } j
admin
2019-12-10
54
问题
设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。
order (int j,int m)
}
int i,ternp;
if(j<m)
{
if(a
<a[j])
{
temp=a
;
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/N13i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
为了在通用操作系统管理下的计算机上运行一个程序,需要经历几个步骤,但是,()不是一定需要。
设需在两台计算机间经两个中间节点传送100M字节的文件,假定:(1)计算机与中间节点间的通信线路以及中间节点间通信线路的通信速率皆为8Kbps;(2)数据传输的差错可以忽略不计;(3)中间节点存储转发时间可忽略不计;
UNIX系统中,输入/输出设备看作是()。
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用的是()。
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
四位运算器框图如下图所示,ALU为算术逻辑单元,A和B为三选一多路开关,预先已通过多路开关A的SW门向寄存器R1,R2送入数据如下:R1=0101,R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下:(1)R1
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:画出有向带权图G。
一个含有n个顶点和e条边的简单无向图,在其邻接矩阵存储结构中零元素的个数是()。
随机试题
在关系模式R(u)中,对于u的子集x和Y,如果X′是X的真子集,X→Y,X′→Y,则称【】
十七岁中学生甲的祖父乙,赠送给其财产10万元。甲欲购买一台价值9000元的笔记本电脑,根据法律规定,甲应当()
描述上颌骨血供特点及临床意义哪项是错误的
MnO2+HCl=MnCl2+Cl2+H2O将反应配平后,MnCl2的系数为()。
甲公司每年年末确认交易性金融资产公允价值变动损益,则2007年12月31日应确认的交易性金融资产公允价值变动损益为( )元。甲公司2008年1月15日出售债券和股票时,应编制的会计分录为( )。
某公司每年(360天)现金需求额为400万元,每次转换的交易成本为20万元,银行的存款利率为10%,则该公司目标现金持有量为( )。
某商场采用售价金额核算法核算库存商品。2015年3月1日,该商场库存商品的进价成本总额为180万元,售价总额为250万元;本月购入商品的进价成本总额为500万元,售价总额为750万元;本月实现的销售收入总额为600万元。不考虑其他因素,2015年3月31日
张老师制作了一个课件,他想在课件的第一页插入一个视频以此吸引学生的注意力,那么张老师可以选择的素材是()。
你单位要制定一个党员评价体系,请问都有哪些因素可以作为标准?
比较直接插入排序、起泡排序、简单选择排序、快速排序、堆排序、2一路归并排序和基数排序的算法性能,并填写下表:
最新回复
(
0
)