问题
单项选择题 共用题干题
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（1）；若采用快速排序算法，则时间和空间复杂度分别为（2）。
空白（1）处应选择（）
A.O（n2）和O（n）
B.O（n）和O（n）
C.O（n2）和O（1）
D.O（n）和O（1）
答案
参考答案：D
解析：本题考查算法分析的基础知识。排序和查找是基本的计算问题，存在很多相关的算法，不同的算法适用于不同的场合。不同的数据输入特点相同的算法也有不同的计算时间。若数据基本有序，对插入排序算法而言，则可以在近似线性时间内完成排序，即O（n）；而对于快速排序而已，则是其最坏情况，需要二次时间才能完成排序，即O（n）。两个算法在排序时仅需要一个额外的存储空间，即空间复杂度均为常数时间复杂度O（1）。