首页
登录
从业资格
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
题库
2022-08-02
60
问题
对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://tihaiku.com/congyezige/2409623.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
线程可以实现在()。①内核空间②用户空间③虚拟空间④物理空间A.①③ B.
查找算法中,()要求查找表进行顺序存储并且按照关键字有序排列,一般不进行表
从时间、地区和商品种类三个维度来分析某电器商品销售数据属于()。A.ETL
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某项目包含的活动如下表所示,完成整个项目的最短时间为()周。不能通过缩短活动(
某项目包含的活动如下表所示,完成整个项目的最短时间为(请作答此空)周。不能通过缩
某小区由于建设时间久远,停车位数量无法满足所有业主的需要,为公平起见,每年进行一
以下加密算法中适合对大量的明文消息进行加密传输的是() A.RSA B.
在Windows系统中,磁盘碎片整理程序可以分析本地卷,以及合并卷上的可用空间使
中国采用的电视的制式是(请作答此空),采用( )彩色空间,它的帧频是( ),电视
随机试题
Manypeoplebelievetheglarefromsnowcausessnowblindness.Yet,darkgla
Moneyisusedforbuyingorsellinggoods,formeasuringvalueandforstori
[originaltext][5]Atthisweek’sCEStechnologyexpo,LGwillbeoneofmany
大流动性混凝土是指拌合物坍落度不低于()的混凝土。A.140mm B.1
A.生后感染性肺炎 B.宫内感染性肺炎 C.新生儿肺透明膜病 D.胎粪吸入
A.脾胃虚弱 B.食滞胃脘 C.湿热蕴脾 D.胃火炽盛 E.胃阴不足饥不
(2021年真题)根据《民法典》下列完全民事行为能力人所立的,且已注明或记录年月
智育就是知识教育。()
女,18岁。近几个月来常因琐事与父母发生激烈争吵,闷闷不乐,被诊断为抑郁症而入院
(2021年真题)某高速公路甲市乙区路段,一辆小型面包车与—辆重型罐车相撞,导致
最新回复
(
0
)