首页
登录
从业资格
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
题库
2022-08-02
68
问题
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为( );若采用快速排序算法,则时间和空间复杂度分别为( )。问题1选项A.O(n2)和O(n)B.O(n)和O(n)C.O(n2)和O(1)D.O(n)和O(1)问题2选项A.O(n2)和O(n)B.O(nlgn)和O(n)C.O(n2)和O(1)D.O(nlgn)和O(1)
选项
答案
DC
解析
本题考查算法分析的基础知识。排序和查找是基本的计算问题。存在很多相关的算法,不同的算法适用于不同的场合。不同的数据输入特点相同的算法也有不同的计算时间。若数据基本有序,对插入排序算法而言,则可以在近似线性时间内完成排序。即
O(n);而对于快速排序而言,则是其最坏情况,需要二次时间才能完成排序,即O(n2)。两个算法在排序时仅需要一个额外的存储空间,即空间复杂度为常数O(1)。(这里比较特殊,基本有序的情况下,快速排序因为不需要做交换处理,所以不需要存储额外数据,每一轮记录一次基准数值,空间复杂度只需要O(1)。)
转载请注明原文地址:https://www.tihaiku.com/congyezige/2409623.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
线程可以实现在()。①内核空间②用户空间③虚拟空间④物理空间A.①③ B.
查找算法中,()要求查找表进行顺序存储并且按照关键字有序排列,一般不进行表
从时间、地区和商品种类三个维度来分析某电器商品销售数据属于()。A.ETL
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某项目包含的活动如下表所示,完成整个项目的最短时间为()周。不能通过缩短活动(
某项目包含的活动如下表所示,完成整个项目的最短时间为(请作答此空)周。不能通过缩
某小区由于建设时间久远,停车位数量无法满足所有业主的需要,为公平起见,每年进行一
以下加密算法中适合对大量的明文消息进行加密传输的是() A.RSA B.
在Windows系统中,磁盘碎片整理程序可以分析本地卷,以及合并卷上的可用空间使
中国采用的电视的制式是(请作答此空),采用( )彩色空间,它的帧频是( ),电视
随机试题
[originaltext]M:Iseeyournewresumethatyouworkedasamanagerofstoreca
A电视剧组为吸引观众眼球,在改编《红岩》时将江姐、许云峰、甫志高三人描述成三角恋
患者,女,25岁,不慎被浓硫酸烧伤颜面部,最佳的紧急处理措施是A.立即前往医院就
A.从鸠尾分出散布于背部 B.从鸠尾分出散布于腹部 C.从鸠尾分出散布于胸部
下列各项中,不符合内部牵制的要求的是()。A、出纳人员管票据 B、出纳人员
为高热患者酒精擦浴时,禁忌擦拭的部位是A.头部和颈部 B.手掌和四肢 C.腋
下边四个图形中,只有一个是由上边的四个图形拼合(只能通过上、下、左、右平移)而成
A.发散 B.条件收敛 C.绝对收敛 D.收敛性不能确定
根据消费税法律制度的规定,下列属于消费税纳税人的有()。A.委托加工白酒的
女,5岁。自幼体弱,易患呼吸道感染,查体:心前区稍隆起,无震颤,胸骨左缘第2~3
最新回复
(
0
)