递归与分治策略

复习#

核心问题：

递归怎么终止？
分治怎么拆？
复杂度怎么用主定理算？
怎么通过“减少子问题个数”优化？

Q&A#

递归的定义
 分治的步骤（3步）
用分治法写归并排序（MergeSort）的伪代码
 分治算法的时间分析与复杂度主定理
 不用主定理怎么分析复杂度（递推/猜测验证）？
快速选择怎么求第 k 大/小？
堆排序怎么建堆和排序？
在纸上快速写一下：最近点对、整数相乘、矩阵乘法的经典算法，并分析时间复杂度

一、递归的概念#

递归的定义#

直接或间接地调用自身的算法称为递归算法；用函数自身给出定义的函数称为递归函数。

双递归函数： 当一个函数及它的一个变量由函数自身定义时，称其为双递归函数。如 Ackerman 函数，有两个独立整型变量，不同变量值定义不同单变量函数，部分无法用非递归定义，复杂度高。

递归的构成要素

递归定义： 通过较小自变量的函数值来定义较大自变量的值（如 $n! = n \times (n-1)!$ ）

初始值（边界条件）： 必须有非递归定义的初始值，否则无法计算。如 $0!=1$ 、 $F(0)=0, F(1)=1$

常见错误
只有递归调用、没有初始值的递归是无限递归，会耗尽栈空间。初始值是递归正确终止的保证。

递归的实现与调用层次#

递归算法执行时多次调用自身，系统为其建立递归调用工作栈
调用前：传实参、分配局部变量存储区、转移控制；返回时：保存结果、释放存储区、转移控制
层次概念： 主算法为第 0 层，每次调用进入下一层；进入一层压栈（新工作记录），退出一层弹栈

递归的优缺点#

	优点	缺点
描述	结构清晰、可读性强	—
验证	易用数学归纳法证明正确性	—
设计调试	方便	—
效率	—	运行效率低，耗费时间空间多
调用开销	—	多次调用/返回增大系统开销
栈空间	—	层次越深占栈越多，可能栈溢出

二、递归经典案例#

阶乘函数#

n! = \begin{cases} 1 & n = 0 \\ n \times (n-1)! & n > 0 \end{cases}

计算 $5!$ 时依次调用 $4!, 3!, 2!, 1!$ ，直到初始值 $0!$ 再逐层返回。

Fibonacci 数列#

F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1) + F(n-2) & n > 1 \end{cases}

注意
Fibonacci 直接递归存在大量重复计算（同一个子问题被多次求解），计算时间呈指数级增长。

Hanoi 塔问题#

将 $n$ 个圆盘从柱子 A 移到 C，规则：每次只移一个，大盘不能放在小盘上。

递归分解：

将 $n-1$ 个圆盘从 A → B（辅助柱 C）
将第 $n$ 个圆盘从 A → C
将 $n-1$ 个圆盘从 B → C（辅助柱 A）

递归的优化#

用用户自定义栈模拟系统递归工作栈，把递归转化为非递归算法
减少/压缩栈操作，提高效率、节省空间
用动态规划消除重复子问题（如 Fibonacci）

三、分治算法基本思想#

分治算法的核心：将复杂问题分解成两个或更多相同/相似的子问题，直到子问题可以简单直接求解，原问题的解是子问题解的合并。

三步走：

分解（Divide）
解决（Conquer） ——递归求解子问题
合并（Combine） —— 把子问题解合并成原问题解

善弈者谋势，不善弈者谋子。结构清晰、分工明确、层层递进。

四、归并排序（MergeSort）#

分：从中间一分为二；治：递归各子问题；合：合并有序子数组。

1
ALG Mergesort(A, l, r):
2
  if l < r:
3
    m ← (l+r) // 2
4
    Mergesort(A, l, m)
5
    Mergesort(A, m+1, r)
6
    merge(A[l..m], A[m+1..r])

实例：38 27 43 3 9 82 10
分的过程（递归到单元素）：
1
38 27 43 3 | 9 82 10
2
38 27 | 43 3 | 9 82 | 10
3
38 | 27 | 43 | 3 | 9 | 82 | 10
合的过程（两两有序合并）：
1
27 38 | 3 43 | 9 82 | 10
2
3 27 38 43 | 9 10 82
3
3 9 10 27 38 43 82

五、分治算法的运行时间分析 ⭐#

一般递归方程#

一个分治算法处理规模 $n$ 的问题，分解为 $a$ 个规模 $n/b$ 的子问题，解决子问题需 $O(f(n))$ ，合并需 $O(g(n))$ ，则：

T(n) = a\,T(n/b) + \dots

$a$ ：子问题数量
$b$ ：子问题规模与原问题规模的比例
$f(n)$ ：解决每个子问题的时间
$g(n)$ ：合并子问题解的时间

我的思考
我这里想过，为什么可以是a!=b，如果是按比例分割，应该是a*b=n吧？
原因就是，砍掉的另一半可能可以丢掉呢？比如二分查找，找了一半找到了就不用找另一半了呀！

主定理（Master Theorem）#

设 $T(N) = a\,T(N/b) + O(N^k \log^p N)$ ，其中 $a \ge 1, b > 1, p \ge 0$ ：

情况	条件	结果
1	$a > b^k$	$T(N) = O(N^{\log_b a})$ （递归开销占主导）
2	$a = b^k$	$T(N) = O(N^k \log^{p+1} N)$
3	$a < b^k$	$T(N) = O(N^k \log^p N)$ （合并开销占主导）

直观理解

定理 1（ $a > b^k$ ）： 递归调用的开销占主导

定理 2（ $a = b^k$ ）： 递归与非递归开销相当

定理 3（ $a < b^k$ ）： 非递归（合并/求解）开销占主导

常见递推式及复杂度#

递推式	典型算法	复杂度
$T(N) = 2T(N/2) + O(N)$	归并排序	$O(N \log N)$
$T(N) = 4T(N/2) + O(N)$	大矩阵乘法优化	$O(N^2)$
$T(N) = 2T(N/2) + O(1)$	找最大/最小、求平均值	$O(N)$
$T(N) = T(N-1) + O(1)$	求阶乘	$O(N)$
$T(N) = 2T(N-1) + O(1)$	全排列问题	$O(2^n)$
$T(N) = 2T(N/2) + O(N\log N)$	快速傅里叶变换 FFT	$O(N \log^2 N)$
$T(N) = T(N/2) + O(1)$	二分查找	$O(\log N)$

不用主定理如何分析？（递归树 / 迭代法 / 猜测验证）#

方法一：迭代法
把递归式不断展开代入，直到规模为常数的终止条件，再把各项累加求和。
以归并排序为例：每一层合并代价为 $O(N)$ ，共 $\log N$ 层，总代价 $O(N \log N)$ 。

方法二：猜测—验证（数学归纳法）
先猜测一个上界，再用数学归纳法验证（基础情形 + 递推步）。
例：猜测归并排序 $T(N) = O(N \log N)$ ，代入 $T(N) = 2T(N/2) + O(N)$ 验证当 $N>1$ 成立。

六、二分查找#

在有序数组中对折查找，每次比较将范围缩小一半。

$T(N) = T(N/2) + O(1) \quad (a=1, b=2) \;\Rightarrow\; O(\log N)$

1
ALG binary_search(A, l, r, target):   # A 升序
2
  if l < r:
3
    m ← (l+r) // 2
4
    if A[m] == target: return m
5
    elif A[m] > target: return binary_search(A, l, m-1, target)
6
    else: return binary_search(A, m+1, r, target)

注意
二分查找必须基于有序数组，否则算法失效。

七、快速排序（QuickSort）#

基本思想： 一趟排序把无序表分成独立两部分，一部分所有元素都比另一部分小，再递归对两部分快排，最终整个表有序。

1
ALG QuickSort(A, low, high):
2
  if low < high:
3
    pivot_index ← Partition(A, low, high)
4
    QuickSort(A, low, pivot_index - 1)
5
    QuickSort(A, pivot_index + 1, high)
6

7
ALG Partition(A, low, high):
8
  # 随机选 pivot，通常选 A[high]
9
  i ← low - 1
10
  for j in range(low, high):
11
    if A[j] <= pivot:
12
      i ← i + 1
13
      swap(A[i], A[j])
14
  swap(A[i+1], A[high])
15
  return i + 1

时间复杂度分析#

情况	条件	复杂度
最好	每次均匀分割（pivot 在中间）	$O(n \log n)$
平均	各排列等概率，pivot 有一定概率得到较平衡划分（如 1:9 或 2:8）	$O(n \log n)$
最坏	每次划分极不均衡（数组已有序/逆序，pivot 是最小/最大，一边 $n-1$ 一边空）	$O(n^2)$

直观理解平均情况
只要平均每次能按常数比例分割（如至少 $1/3 : 2/3$ ），递归深度为 $O(\log n)$ ，每层总共处理 $n$ 个元素，总时间仍趋近 $O(n \log n)$ 。

经典排序算法对比#

算法	最坏	最好	平均	方法
MergeSort	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	分治
QuickSort	$n^2$	$O(n\log n)$	$O(n\log n)$	分治
InsertSort	$n^2$	$n$	$n^2$	插入
SelectSort	$n^2$	$n^2$	$n^2$	选择
BubbleSort	$n^2$	$n$	$n^2$	交换
HeapSort	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	堆/交换

注意

归并、堆排序稳定且始终 $O(n\log n)$ ；快速排序平均快但最坏退化 $O(n^2)$

快速选择（QuickSelect）：利用 Partition 求”第 k 大/小”， $T(N) = T(N/2) + N \Rightarrow O(N)$

堆排序（HeapSort）#

老师课上补充复习：堆排序既非递归也不靠二分分治，讲它主要是用来引出”空间复杂度”的概念。堆是一种完全二叉树，用数组顺序存储。

数组存储的下标规则（0 基，🔴 常考）：

$H[h]$ 的左孩子： $H[2h+1]$
$H[h]$ 的右孩子： $H[2h+2]$
$H[h]$ 的父结点： $H[\lfloor (h-1)/2 \rfloor]$

大顶堆性质： 根是最大值，且每个父结点 $\ge$ 其子结点（小顶堆则 $\le$ ）。

两部分操作：

建堆（Build-Heap）： 从最后一个非叶子结点开始，从后往前逐个结点执行”下沉（sift down）“，使整棵树满足堆性质。复杂度 $O(n)$ 。
排序： 反复把堆顶（当前最大值）交换到序列末尾，堆大小减 1，再对剩余部分”下沉”恢复堆性质，循环 $n$ 次。每次调整 $O(\log n)$ ，总 $O(n\log n)$ 。

复杂度对比

指标 HeapSort 说明
时间最好/平均/最坏均 $O(n\log n)$ 最坏也不退化
空间 $O(1)$ 原地 只用了数组本身，几乎无额外空间（这就是老师引入的”空间复杂度”概念）
稳定性不稳定相同值位置可能互换

与快速排序对比：快排平均快但最坏 $O(n^2)$ 、需 $O(\log n)$ 栈空间；堆排序最坏稳定 $O(n\log n)$ 且原地 $O(1)$ 空间，但常数因子较大、缓存不友好。

指标	HeapSort	说明
时间	最好/平均/最坏均 $O(n\log n)$	最坏也不退化
空间	$O(1)$ 原地	只用了数组本身，几乎无额外空间（这就是老师引入的”空间复杂度”概念）
稳定性	不稳定	相同值位置可能互换

八、分治进阶案例 ⭐#

我的思考
重点是用更多的加减法换更少的乘除法！
加减法在单层递归中是O(1)！！！

1. 最近点对问题（最小距离问题）#

平面上有 $N$ 个点，找距离最近的两个点。

分治步骤：

分割： 按 x 坐标排序，画垂线把点集分为 $P_L, P_R$ 两半
递归求解： 递归求两半内部的最近点对 $d_L, d_R$
合并： 处理跨越两半的最近点对 $d_C$ ，最终 $\delta = \min(d_L, d_R, d_C)$

如何高效计算 dC

只考虑与中间线距离小于 $\delta$ 的条带（strip）中的点

条带内点按 y 坐标排序

在 $\delta \times \delta$ 区域内，任意两点距离至少为 $\delta$ 时最多 4 个点，故 $2\delta \times \delta$ 区域最多 8 个点。对每个点 $p_i$ 最多只比较 7 个点即可

这样合并代价 $d_C = O(N)$

复杂度： 排序 $O(N\log N)$ ，递归 $T(N)=2T(N/2)+O(N)=O(N\log N)$ ，空间 $O(N)$ 。总时间 $O(N\log N)$ 。

2. 整数相乘问题（Karatsuba 算法）#

两个 $N$ 位数相乘，传统竖式乘法需 $N^2$ 次乘法。

分块： $X = X_L 10^{N/2} + X_R$ ， $Y = Y_L 10^{N/2} + Y_R$

$XY = X_L Y_L 10^N + (X_L Y_R + X_R Y_L) 10^{N/2} + X_R Y_R$

直接展开需 4 次乘法： $T(N) = 4T(N/2) + O(N) \Rightarrow O(N^2)$ ，无改进。

Karatsuba 技巧 —— 把 4 次乘法降为 3 次
发现恒等式：
$X_L Y_R + X_R Y_L = (X_L - X_R)(Y_R - Y_L) + X_L Y_L + X_R Y_R$
其中 $X_L Y_L$ 和 $X_R Y_R$ 已经算过，只需额外算 1 次乘积 $(X_L - X_R)(Y_R - Y_L)$ 。于是递归式变为：
$T(N) = 3T(N/2) + O(N) \Rightarrow T(N) = O(N^{\log_2 3}) = O(N^{1.59})$

进一步优化：

Toom-Cook 3-way： 分成三等分，直接 $9T(N/3)+O(N) = O(N^2)$ ；优化后 $5T(N/3)+O(N) = O(N^{1.47})$
终极目标：Harvey & van der Hoeven (2019) 实现 $O(N \log N)$ 的大整数乘法（《Annals of Mathematics》）

复杂度增长对比
$O(N^2) > O(N^{1.59}) > O(N^{1.47}) > O(N^{1+\varepsilon}) > O(N \log N)$
注意 $N\log N = o(N^{1+\varepsilon})$ （小 $o$ 表示严格更慢增长）。

3. 矩阵乘法（Strassen 算法）#

两个 $N \times N$ 矩阵相乘，传统 $O(N^3)$ （ $N^2$ 个元素，每个元素 $N$ 次乘法）。

普通分块： 分块 $8$ 次矩阵乘法： $T(N) = 8T(N/2) + O(N^2) = O(N^3)$ ，无改进。

Strassen 技巧 —— 把 8 次乘法降为 7 次
将两矩阵各分成 4 个 $N/2$ 子矩阵，通过 7 个中间矩阵（而非 8 个）的乘积组合出最终结果：
$T(N) = 7T(N/2) + O(N^2) \Rightarrow T(N) = O(N^{\log_2 7}) = O(N^{2.81})$

进阶案例的共同思路
无论是 Karatsuba、Toom-Cook 还是 Strassen，核心都是：用更多的加/减法，换取更少的大规模乘法，从而把递归式中的 $a$ （子问题个数）降下来。代价是常数项的加/减法开销增加，但渐近复杂度显著下降。

九、本章小结#

递归：自身调用自身，必须有初始值；结构清晰但效率低，可用栈+动态规划优化
分治：分 → 治 → 合三步，归并排序、二分查找、快排都是典型
主定理：解析 $T(N) = aT(N/b) + O(N^k\log^p N)$ 三类情况的复杂度
优化核心：降低分治递归中的子问题个数 $a$ （Karatsuba、Strassen 均属此类），换取渐近复杂度下降