首页
登录
从业资格
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
题库
2022-08-02
75
问题
对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系统中,磁盘碎片整理程序可以分析本地卷,以及合并卷上的可用空间使
中国采用的电视的制式是(请作答此空),采用( )彩色空间,它的帧频是( ),电视
随机试题
Inthispart,youarerequiredtowriteanessayofnolessthan200wordsonWh
Blindpeoplecan"see"thingsbyusingotherpartsoftheirbodies.Thisfac
ThemenuatSpyce,whichopenstodayindowntownBoston,isn’tnoticeablydi
同说汉语,同写汉字,读一本历史,抚一张古琴。文化像氧气,融化在血液中……13亿2
主流的股价预测模型有()。 Ⅰ.神经网络预测模型 Ⅱ.灰色预测模型
以大批量生产的效率向客户提供多种定制产品的生产模式是()。A:项目型生产模式
预计在一个正常营业周期中清偿的债务是()。A.流动负债 B.在建工程 C
某大型企业集团拟建设年设计生产能力200万吨非煤矿山建设项目和跨甲乙两省输送距离
根据《建设项目环境影响评价资质管理办法》,环评机构应当建立其主持编制的环境影响报
对比较法中常有的形式说法错误的是()。A.将实际指标与上期实际指标对比 B.将
最新回复
(
0
)