第66章 算法的时间和空间效率分析

66.1 复杂度分析方法

66.1.1 时间复杂度分析方法

1. 找出算法中的基本操作：赋值、比较、算术运算等与问题规模强相关的操作。
2. 统计基本操作总执行次数，记为函数$T(n)$，$n$为输入规模。
3. 简化：仅保留最高阶项、丢弃系数，得到时间复杂度。

66.1.2 空间复杂度分析方法

1. 统计程序占用所有存储空间：输入、代码、常量、临时变量、数组、栈等。
2. 提取随$n$变化的存储开销，记$S(n)$。
3. 简化得到空间复杂度，只保留最高阶项。

66.2 各类算法复杂度分析

66.2.1 排序算法

冒泡排序

• 时间复杂度：平均、最坏$O(n^2)$；完全有序最优$O(n)$
• 空间复杂度：$O(1)$，仅交换临时变量

快速排序

• 时间复杂度：平均$O(n\log n)$；数组有序/逆序最坏$O(n^2)$
• 空间复杂度：$O(\log n)$（递归栈深度），最坏$O(n)$

归并排序

• 时间复杂度：最优/平均/最坏统一$O(n\log n)$
• 空间复杂度：$O(n)$，需要辅助数组存储合并结果

66.2.2 查找算法

顺序查找

• 时间：最好$O(1)$，平均/最坏$O(n)$
• 空间：$O(1)$

二分查找

• 时间：最好$O(1)$，平均/最坏$O(\log n)$
• 空间：迭代$O(1)$；递归$O(\log n)$（递归栈）

66.2.3 树遍历（前/中/后序）

• 时间复杂度：$O(n)$，每个节点访问一次
• 空间复杂度：$O(h)$，$h$为树高；平衡树$O(\log n)$，斜树$O(n)$

66.2.4 图遍历 DFS / BFS

• 时间复杂度：$O(V+E)$，$V$顶点数，$E$边数
• 空间复杂度：$O(V)$（栈/队列、访问标记数组）

66.2.5 暴力深度/广度搜索（迷宫等）

• 时间：$O(b^d)$，$b$分支数，$d$搜索深度
• 空间：$O(b^d)$

66.2.6 分治算法

递推式$T(n)=k \cdot T(n/k)+D(n)+C(n)$，归并排序是典型例子，时间$O(n\log n)$。

66.2.7 动态规划

• 一维DP：时间$O(n)$
• 二维DP（LCS、区间DP）：时间$O(n^2)$
• Floyd图全最短路：$O(n^3)$ 空间可通过滚动数组从$O(n^2)$压缩至$O(n)$

66.3 复杂度等级从快到慢

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < 2^n$