14.2.1 时间复杂度与空间复杂度-01

本节重点是从代码结构中识别时间复杂度。考试不会让你精确数每一条机器指令，而是让你判断基本操作的增长规模。

基本操作

分析复杂度时，先找最能代表算法成本的基本操作，例如比较、赋值、循环体执行、数组访问等。基本操作执行次数随 $n$ 如何增长，就是时间复杂度的来源。

常见代码结构

代码形态	复杂度	判断依据
顺序执行固定条语句	$O(1)$	与 $n$ 无关
单层循环 for i=1..n	$O(n)$	循环 $n$ 次
双重独立循环	$O(n^2)$	$n\times n$
每次规模减半	$O(\log n)$	如二分查找
外层 $n$，内层 $\log n$	$O(n\log n)$	常见于部分排序/树操作

对数复杂度为什么小于线性

二分查找每次把问题规模减半。规模从 $n$ 变成 $n/2,n/4,n/8...$，直到 1，次数约为：

$${\log }_{2}n$$

因此 $O(\log n)$ 增长远慢于 $O(n)$。

排序中的 $O(n\log n)$

课程提前点到：堆排序、归并排序、快速排序常出现 $O(n\log n)$。

算法	为什么是 $n\log n$
堆排序	每次调整堆约 $\log n$，重复 $n$ 次
归并排序	分割层数约 $\log n$，每层合并总量 $n$
快速排序	平均分割层数约 $\log n$，每层处理 $n$

指数级复杂度

$O(2^n)$ 常来自“每个位置都有选或不选两种可能”。例如长度为 $n$ 的序列，其子序列数量可用二进制选择表示，每个位置 0/1，共 $2^n$ 种。

指数级增长很快，通常意味着暴力穷举成本很高，后续可能需要动态规划、剪枝或贪心等策略改进。

本节例题

单选

每一步把问题规模减半，直到规模为 1，这类过程通常是：

AO(1)BO(log n)CO(n)DO(n²)

自查清单

1. 能否从循环层数初步判断复杂度？
2. 能否解释二分查找为什么是 $O(\log n)$？
3. 能否识别哪些问题可能出现 $O(2^n)$？