Logo

菜单

kyrie
kyrie
发布于 2025-11-03 / 26 阅读
0
0

递归与分治

递归

  • 是什么：函数（或过程）直接或间接地调用自己。

  • 三件套：

    1. 基例（最小规模的直接答案）；

    2. 缩小规模（每次更接近基例）；

    3. 组合返回（把子结果做成父结果）。

  • 作用：一种实现技巧/控制流，很多思路都能用递归写（DFS、树遍历、回溯、分治、带记忆化的 DP 等）。

  • 优缺点：代码简洁、贴合问题结构；但有函数开销与栈深度风险，易写出指数级重复计算（如朴素斐波那契）。

伪代码：

def solve(x):
    if base(x): return ans
    sub1 = solve(smaller(x,1))
    sub2 = solve(smaller(x,2))
    return combine(sub1, sub2)

分治

  • 是什么：一种算法设计范式，口号是“分—解—合”：

    • 分：把规模为 n 的问题拆成 a 个更小的子问题（通常规模 n/b）；

    • 解：对子问题递归求解；

    • 合：把子问题解合成为原问题解（代价 f(n)）。

  • 关键要求：子问题相互独立或重叠很少；合并成本可控。

  • 典型例子：二分查找、归并排序、快速排序、Karatsuba 大整数乘法、Strassen 矩阵乘法、最近点对、FFT。

伪代码：

def divide_and_conquer(A):
    if small(A): return solve_trivially(A)
    A1, A2, ... , Aa = split(A)
    R1, R2, ... , Ra = [divide_and_conquer(Ai) for Ai in parts]
    return merge(R1, R2, ... , Ra)

二者关系与区别

  • 递归是“怎么写”的手段；分治是“怎么想”的范式。

  • 分治通常用递归实现，但并非所有递归都是分治：

    • 朴素斐波那契递归有大量重叠子问题，不满足“独立子问题”，更像 DP/记忆化的舞台。

    • 树的先序遍历是递归，但几乎没有“合并代价”的分治结构需求。

  • 当子问题大量重叠且需要重复利用历史结果，优先考虑动态规划（DP）或“递归+记忆化”。

何时用

  • 分治：能把问题稳定拆小、子问题基本独立、合并步骤清晰（排序、几何、信号处理）。

  • 递归：问题自带树/层级结构或天然自相似（树与图遍历、回溯搜索、表达式求值）。

例子

二分检索递归实现

目标：在升序有序数组 a 中查找值 x 的位置；找不到返回 -1 。

递归思路：每次用中点 mid 把区间一分为二，只在可能存在解的那一半继续递归。

闭区间写法 [l,r]

递归不变式：若目标存在于当前区间，则落在 [l..r] 内。

终止条件

  • l>r ：区间空，返回 -1 。

递归推进

  • mid = l + (r - l) // 2（避免溢出）

  • 若 a[mid]=x：命中；

  • 若 a[mid]<x：递归右半区 [mid + 1, r]；

  • 否则递归左半区 [l, mid - 1]。

def bsearch_rec(a, x, l, r):
    if l > r:
        return -1
    mid = l + (r - l) // 2
    if a[mid] == x:
        return mid
    elif a[mid] < x:
        return bsearch_rec(a, x, mid + 1, r)
    else:
        return bsearch_rec(a, x, l, mid - 1)

# 入口
def bsearch(a, x):
    return bsearch_rec(a, x, 0, len(a) - 1)

复杂度与递推

  • 递推：T(n)=T(n/2)+O(1)

  • 时间复杂度： \mathcal{O}(logn)

  • 空间复杂度：递归栈 \mathcal{O}(logn)

逆序对计数

设计思路

把区间一劈两半：

  • 分：把 A[l..r] 划分为左右两段 A[l..m] 、A[m+1..r] 。

  • 解：分别递归统计左右段内部的逆序对数。

  • 合：在“归并”两个有序段时顺带统计跨段逆序对：
    当右段元素 A[j] < A[i] 被先取走时，说明左段从 i 到 m 的所有剩余元素都大于 A[j] ，形成 m-i+1 个跨段逆序对，一次性加上即可。
    注意逆序对定义是 A[i] > A[j] ，所以相等不计数，归并时写成 <= 走左边能自然避坑并保持稳定。

伪代码

function countInv(A[1..n]):
    temp[1..n]
    return solve(A, 1, n, temp)

function solve(A, l, r, temp):
    if l >= r: return 0
    m = (l + r) // 2
    ans = 0
    ans += solve(A, l, m, temp)
    ans += solve(A, m + 1, r, temp)
    ans += mergeCount(A, l, m, r, temp)
    return ans

function mergeCount(A, l, m, r, temp):
    i = l; j = m + 1; k = l
    cnt = 0
    while i <= m and j <= r:
        if A[i] <= A[j]:              // 相等不计逆序
            temp[k] = A[i]; i += 1
        else:                          // A[i] > A[j]，产生跨段逆序
            temp[k] = A[j]; j += 1
            cnt += (m - i + 1)         // 左段剩余都比 A[j] 大
        k += 1
    while i <= m: temp[k] = A[i]; i += 1; k += 1
    while j <= r: temp[k] = A[j]; j += 1; k += 1
    for t from l to r: A[t] = temp[t]  // 写回
    return cnt

时间复杂度

递推式：T(n)=2T(n/2)+Θ(n)（两次递归 + 线性归并）。
由主定理得：T(n)=Θ(nlog⁡n)；
空间：辅助数组与递归栈，O(n)

额外空间，栈深 O(log⁡n)。

最大子数组

分治思路（递归）

把区间 [l, r] 对半分成 [l, m] 与 [m+1, r]（其中 m = (l+r)/2）。最大子数组要么：

  1. 完全在左半边；

  2. 完全在右半边；

  3. 跨过中点（左半结尾 + 右半开头拼起来）。

跨中点的最大和 = “左半最大后缀和” + “右半最大前缀和”。

伪代码

function maxSubarray(a, l, r):
    if l == r:
        return (a[l], l, r)            // (最大和, 左端点, 右端点)

    m = (l + r) // 2
    (Lsum, Ll, Lr) = maxSubarray(a, l, m)
    (Rsum, Rl, Rr) = maxSubarray(a, m+1, r)

    // 计算跨中点的最大和：左半最大后缀 + 右半最大前缀
    bestLeftSuffix = -∞; sum = 0; idxL = m
    for i from m downto l:
        sum += a[i]
        if sum > bestLeftSuffix:
            bestLeftSuffix = sum
            idxL = i

    bestRightPrefix = -∞; sum = 0; idxR = m+1
    for j from m+1 to r:
        sum += a[j]
        if sum > bestRightPrefix:
            bestRightPrefix = sum
            idxR = j

    crossSum = bestLeftSuffix + bestRightPrefix
    // 三者取最大
    if Lsum >= Rsum and Lsum >= crossSum:
        return (Lsum, Ll, Lr)
    else if Rsum >= Lsum and Rsum >= crossSum:
        return (Rsum, Rl, Rr)
    else:
        return (crossSum, idxL, idxR)

复杂度与空间

  • 递推式：T(n) = 2T(n/2) + O(n)（每层线性求两次前/后缀）。

  • 主定理：T(n) = O(n log n)。

  • 额外空间：递归栈 O(log n)；若只存常数变量，辅助空间 O(1)。

动态规划
绪论

评论