【数据结构】考点十九：时间复杂度与空间复杂度_常考空间时间复杂度

【考试临时抱佛脚】系列文章针对于<学习时间少>、<时间紧迫>、<想短时间提升成绩>的考生打造。无论你是<自考>、<专升本>还是<考研>这个专栏都适合你，Let’s go！

一、方法

1）时间复杂性大小顺序：

• O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n² ) < O(n³)
• 有效：对数、幂、乘积
• 无效：指数大于等于2

2）分类及简称总结：
① 快希归堆 ：快（快速排序）、希（希尔排序）、归（归并排序）、堆（堆排序）
② 快希选堆 ：快（快速排序）、希（希尔排序）、选（选择排序）、堆（堆排序）
③ 其它排序：冒泡排序、选择排序、插入排序、平方排序
3）时间复杂度总结：

• 快希归堆 ：O(nlog₂n)
• 其它排序：O(n²)
• 二分查找算法的平均时间复杂度为：O(log₂n)
• 顺序表插入：时间复杂度O(log₂n)
• 顺序表删除：平均时间复杂度为O(n)

4）辅助存储空间的空间复杂度：O(1)
5）排序的稳定性总结：

• 快希选堆：不稳定
• 其它：稳定

二、考察形式1（选择题）

1、问题

1、若长度为 n 的线性表采用顺序存储结构,在其第 i (1<i<n+1)个位置插入一个新元素的算法的时间复杂度为（C）
A. O(1)
B. O(log₂n)
C. O(n)
D. O(n²)

2、在表长为 n 的顺序表上做删除运算,其平均时间复杂度为（B）
A. O(1)
B. O(n)
C. O(log₂n)
D. O(n²)

3、对n个记录的文件进行快速排序,所需要的辅助存储空间的空间复杂度为（A）
A. O(1)
B. O(n)
C. O(log₂n)
D. O(n²)

4、若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（B）
A.对数阶量级复杂性大于线性阶量级
B.对数阶量级复杂性小于线性阶量级【O(log₂n) < O( n )】
C.对数阶量级复杂性等于线性阶量级
D.两者之间无法比较

5、归并排序的空间复杂度是多少？（B）
A. O(1)
B. O(n)
C. O(n log n)
D. O(n^2)

三、考察形式2（填空题）

1、问题

1、就平均时间性能而言,快速排序方法的时间复杂度为 【O(nlog₂n)】
2、二分查找算法的时间复杂度为 【O(log₂n)】
3、对于具有n个元素的数据序列，采用二叉排序树查找，其平均查找长度为 【1+4log₂n】。
4、冒泡排序的平均时间复杂度为 【O(n²)】
5、表长为n的顺序表插入算法的平均移动次数约为 【n/2】
6、直接插入排序的空间复杂度为 【O(1)】
7、二分查找算法的平均时间复杂度为 【O(log₂n)】
8、对顺序表执行插入操作，其插入算法的平均时间复杂性为 【n/2】
9、在最坏情况下,即对几乎已是排好序的输人序列,快速排序算法的效率较低,此时其时间复杂度近似为 【O(n²)】
10、在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为 【0】 次
11、对于具有n个元素的数据序列，若采用二分查找法，当 n 值较大时其平均查找长度为 【log₂(n+1) -1】
12、对顺序表执行删除操作，其删除算法的平均时间复杂性为 【 (n-1)/2 】