2. 从业资格
  3. 对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（　　

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（　　

题库2022-08-02  47
问题 对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
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)