首页
登录
从业资格
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(
题库
2022-08-02
61
问题
对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系统中,磁盘碎片整理程序可以分析本地卷,以及合并卷上的可用空间使
中国采用的电视的制式是(请作答此空),采用( )彩色空间,它的帧频是( ),电视
随机试题
Afewmonthsago,millionsofpeopleinLondonheard【B1】______alloverthet
医疗事故鉴定中,医学会自接到当事人提交的有关医疗事故技术鉴定的材料之日起,出具医
劳务分包合同的价格形式有单价合同和总价合同两种,单价合同有()形式。A.3种
男性患者,60岁,吸烟史40年,登楼梯气急5年,对诊断肺气肿最有意义指标是A.动
国家药品不良反应监测中心应A.每一年向国家食品药品监督管理局报告药品不良反应监测
男性,30岁,不慎被车撞伤致骨盆骨折,不能排尿,置尿管顺利,但无尿液引出,自尿管
A.八角茴香 B.辛夷 C.川芎 D.厚朴 E.荆芥全草富含挥发油的药材
药物体内血药浓度消除一半所需要的时间,称为A.生物利用度 B.绝对生物利用度
商品归类题 生漆()
【教材变动】从甲、乙两地采购某工程材料,采购量及有关费用如下表所示。该工程材料的
最新回复
(
0
)