14.2 时间复杂度与空间复杂度

复杂度用来评价算法资源消耗。时间复杂度看基本操作随问题规模增长的次数，空间复杂度看算法运行过程中额外占用的辅助空间。

时间复杂度看增长阶

时间复杂度通常记为 $T(n)$，其中 $n$ 是问题规模。渐近分析时，只保留最高增长阶，忽略常数和低阶项：

$$T(n)=3n^2+100n+8\Rightarrow O(n^2)$$

课程中提到大 $O$、$\mathrm{\Theta }$、$\mathrm{\Omega }$ 分别表示渐近上界、紧确界和下界，但软件设计师考试通常主要把它们按“大 O 量级”理解。

常见增长阶

从低到高大致为：

$$O(1)<O({\log }_{2}n)<O(n)<O(n{\log }_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$$

量级	名称	常见场景
$O(1)$	常量级	数组随机访问、交换变量
$O(\log n)$	对数级	二分查找
$O(n)$	线性级	顺序扫描
$O(n\log n)$	线性对数级	堆排序、归并排序、平均快速排序
$O(n^2)$	平方级	双重循环、简单排序
$O(2^n)$	指数级	穷举子集、朴素递归

空间复杂度看辅助空间

空间复杂度不是把输入数据本身全部算进去，而是看算法执行时额外申请的临时空间。课程举了排序中 temp 变量的例子：原数组是输入参数，不算辅助空间；用于交换的临时变量才算。

情况	是否算辅助空间
输入数组 A	通常不算
交换变量 temp	算，$O(1)$
新建长度为 $n$ 的数组	算，$O(n)$
递归调用栈	算，取决于递归深度

本节例题

单选

$T(n)=5n^2+20n+100$ 的渐近时间复杂度是：

AO(1)BO(n)CO(n²)DO(2ⁿ)

自查清单

1. 能否按增长速度给常见复杂度排序？
2. 能否解释为什么常数系数会被忽略？
3. 能否区分输入空间和辅助空间？