首页
登录
从业资格
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
题库
2022-08-02
71
问题
对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系统中,磁盘碎片整理程序可以分析本地卷,以及合并卷上的可用空间使
中国采用的电视的制式是(请作答此空),采用( )彩色空间,它的帧频是( ),电视
随机试题
Theenergycontainedinrockwithintheearth’scrustrepresentsanearlyun
应届毕业生graduatingstudent;currentyear’sgraduate
滨河湿地占一级流域湿地总面积比例最大的河流是:() A.淮河 B.黄河
共用题干 某开发商为促销楼盘,在醒目位置贴出告示:“新房上市,10月1日开始出
A.1.5 B.1.7 C.1.9 D.2.1
我国个人定期存款分为四类,其中零存整取类型的起存金额为()。A.50元
程序化策略中()是模型设计与构建的核心。A.模型的通用性 B.模型适用的周期
一般保证的保证人未约定保证期间的,保证期间为主债务履行期届满之日起()个月A.6
下列哪项不是引起管样呼吸音的因素A.肺组织实变 B.肺脓肿 C.压迫性肺不张
患者,男,20岁。3年前无明显诱因渐起孤僻少语,不愿参加集体活动,甚至与父母也很
最新回复
(
0
)