分治法分析

了解了归并排序的实现原理和循环不变式, 我们将要讨论归并排序的时间复杂度.

分而治之的特点是递归式的, 所以我们一般采用分段函数, 在 基线条件(Base Case) 和 一般条件 分别进行讨论. 首先我们将数据规模定为 $n$ , 按照之前的定义, 时间复杂度为 $T(n)$ . 对于一个常量 $c$ , $n\le c$ 时, 可以直接求解, 时间复杂度总为常数时间$\Theta (1)$. 此时, 基线条件就是 $n\le c$. 一般条件下, 我们要将其分为多个子问题, 假设分成 $a$ 个子问题, 每个子问题的规模为原问题的 $\frac{1}{b}$, 那么消耗的时间则为 $aT(\frac{n}{b})$. 这个时候再加上合并($C(n)$)和分解问题($D(n)$)所需要的时间, 就得到了递归式: $$T(n)=\{\begin{array}{ll}\Theta (1)& \text{if }n\le c,\\ aT\left(\frac{n}{b}\right)+C(n)+D(n)& \text{otherwise.}\end{array}$$

假定归并排序的输入规模 $n$ 是 $2$ 的幂次, 此时分解总产生两个规模均为 $n/2$ 的子问题, 当$n>1$(基线条件: $n\le 1$)时, 有:

• 分解(Divide): 分解过程仅仅计算数组的中间项, 需要常数时间, 即 $D(n)=\Theta (1)$.
• 解决(Conquer): 我们递归地求解两个规模均为 $n/2$ 的子问题, 将贡献 $2T(n/2)$ 的时间复杂度.
• 合并(Combine): 我们证过在一个具有 $n$ 个元素的子数组上过程MERGE(即辅助函数)需要 $\Theta (n)$ 的时间, 所以 $C(n)=\Theta (n)$.

对于归并排序又恰知 $a=b=2$, 即有递归式: $$T(n)=\{\begin{array}{ll}\Theta (1)& \text{if }n\le 1\text{这里也可为}n=1,\\ 2T\left(\frac{n}{2}\right)+\Theta (n)& \text{if }n>1\end{array}$$

后面我们会学一个“主定理“, 用它可得 $T(n)=\Theta (n\log n)$. 这里省略了底数$2$, 即此处的$\log$等价于${\log }_2$. 除非另有明确说明, 这是算法分析中的默认约定(而非数学中的). 许多高效算法通常将问题一分为二, 计算机科学中许多操作基于二进制, 故$\log$非常有效¹.

事实上, 在渐进界($\Theta$)中, $\log$底数影响不大. 以${\log }_{2}n$为例, 利用换底公式, 可得${\log }_{2}n=\frac{{\log }_{x}n}{{\log }_{x}2}={\log }_{2}x\times {\log }_{x}n$. 其中$x$为大于$1$的常数, 所以${\log }_{2}x$也是常数, 省略常数, 得到${\log }_{2}n=\Theta (lo{g}_{x}n)$, 印证了我们上面的结论. 其实忽略底数的本质是对数增长速率的一致性和常数因子的无关性. ²

为了直观地理解上递归式的解为什么是$T(n)=\Theta (n\log n)$, 我们并不需要主定理. 把上递归式重写为: $$T(n)=\{\begin{array}{ll}c& \text{if }n=1,\\ 2T\left(\frac{n}{2}\right)+cn& \text{if }n>1\end{array}$$ 其中常量 $c$ 代表求解规模为 $1$ 的问题所需的时间(等价于 $\Theta (1)$ ), 以及在分解步骤与合并步骤处理每个数组元素所需的时间. 然后我们用 递归树 来展示一下这个过程:

graph TD
    A["cn"] --> B["cn/2"]
    A --> C["cn/2"]

    B --> D["cn/4"]
    B --> E["cn/4"]

    C --> F["cn/4"]
    C --> G["cn/4"]

    D -.-> H["..."]
    D -.-> I["..."]
    E -.-> J["..."]
    E -.-> K["..."]
    F -.-> L["..."]
    F -.-> M["..."]
    G -.-> N["..."]
    G -.-> O["..."]

    H --> P["c"]
    I --> Q["c"]
    J --> R["c"]
    K --> S["c"]
    L --> T["c"]
    M -.-> U["..."]
    N --> V["c"]
    O --> W["c"]

这个完整的递归树有${\log }_{2}n+1$层(分解层数和最后一层), 每一层贡献了$cn$的代价, 总量为$cn\times ({\log }_{2}n+1)=\Theta (n\log n)$.

深入

为了严谨起见, 我们对文中所涉及的“编程范式“和“编程策略“概念进行明确定义:

• 编程范式(Programming Paradigm) : 指代程序代码组织的基本思想和哲学框架, 它规定了程序的结构化方式和核心的抽象机制
• 编程策略(Programming Strategy) : 指代解决特定问题的具体方法论或战术, 指导如何将问题分解并最终实现目标

二者关键区别在于其抽象层级和作用范围. 例如, 面向对象编程(OOP)是一种范式；而增量法(Incremental Approach)则是一种策略. 两者定义上的潜在重叠可能引起混淆. 以“分而治之“为例:

其名称虽带有哲学意味, 但本身并非编程范式. 因为它并未规定代码的具体结构或引入新的语言抽象. 相反, “分而治之“作为一种通用的分解思想, 更适用于策略层面, 这与增量法属于同一层级.

与之对照的, 在Rust编程中常用的 范型(Generics) 则是一种确切的编程范式, 因为它通过参数化类型极大地约束和改变了代码的结构与抽象方式.

迭代(Iterative Approach) 和 递归(Recursive Approach) 是分别实现 增量法 和 分治法 这两类策略的常见具体代码形式:

• 迭代: 通过循环结构逐步逼近目标.
• 递归: 通过自我调用来分解和解决问题.

简单来说,

• 增量法本质上是一种线性扩张: 问题被分解为一系列线性步骤, 答案通过逐步累积增量结果构建.
• 分治法本质上是树状分解: 问题被递归地分解为相互关联的子问题(常形成树状结构), 最终答案通过组合子问题的答案获得.

因而

• 即使使用递归实现的插入排序, 其问题求解模式仍是增量策略.
• 即使使用迭代实现的归并排序, 其问题求解模式仍是分治策略. 递归与迭代作为实现形式, 在理论上可以互相转换.

插入排序

基于上面的理论依据, 现在我们可以把插入排序表示为如下的一个递归过程. 为了排序A[1..n], 我们递归地排序A[1..n-1], 然后把A[n]插入已排序的数组A[1..n-1]. 为插入排序的这个递归版本的最坏情况时间复杂度写一个递归式.

我们先给出一个Rust实现:

pub fn insert_sort_by_recursion<T: Ord>(arr: &mut [T]) {
    // 基本情况: 数组长度为 0 或 1 时已经有序
    if arr.len() <= 1 {
        return;
    }

    let n = arr.len();

    // 递归排序前 n-1 个元素
    insert_sort_by_recursion(&mut arr[..n - 1]);

    // 将最后一个元素插入到已排序的前 n-1 个元素中
    let mut i = n - 1;
    while i > 0 && arr[i - 1] > arr[i] {
        arr.swap(i - 1, i);
        i -= 1;
    }
}

fn main() {
    // 测试用例
    let mut arr = [5, 2, 4, 6, 1, 3];
    println!("排序前: {:?}", arr);

    insert_sort_by_recursion(&mut arr);
    println!("排序后: {:?}", arr);

    let mut empty_arr: [i32; 0] = [];
    insert_sort_by_recursion(&mut empty_arr);
    println!("空数组: {:?}", empty_arr);

    let mut single_arr = [7];
    insert_sort_by_recursion(&mut single_arr);
    println!("单元素数组: {:?}", single_arr);
}

先观察其基线情况: 当数组长度为1时(即 n = 1), 数组已经是有序的, 不需要任何操作, 故 $$T(n)=\Theta (1)\text{ if }n=1$$

Note

其实$n\le 1,n\in \mathbb{N}$更精准(n = 0时为空数组).

然后, 我们进行递归式分析. 因为为了排序A[1..n], 我们递归地排序A[1..n-1], 所以$T(n)=T(n-1)+\Theta (n)$ (其中$\Theta (n)$是进行插入的时间复杂度). 综上则有:

$$T(n)=\{\begin{array}{ll}T(n-1)+\Theta (n)& \text{if }n>1,\\ \Theta (1)& \text{if }n=1.\end{array}$$

我们可以进一步分析, 对递归式展开:

$$\begin{array}{rl}T(n)& =T(n-1)+c\cdot n\\ & =T(n-2)+c\cdot (n-1)+c\cdot n\\ & =T(n-3)+c\cdot (n-2)+c\cdot (n-1)+c\cdot n\\ & ⋮\\ & =T(1)+c\cdot 2+c\cdot 3+\cdots +c\cdot n\\ & =d+c\cdot (2+3+\cdots +n)\\ & =d+c\cdot \left(\frac{n(n+1)}{2}-1\right)\\ & =\Theta (n^2)\end{array}$$ 可见递归版插入排序与迭代版最坏时间复杂度一致.

练习与回答

1. 使用数学归纳法证明: 当$n$刚好是$2$的幂时, 以下递归式的解是$T(n)=n\log n$. $$T(n)=\{\begin{array}{ll}2& \text{if }n=2,\\ 2T\left(\frac{n}{2}\right)+n& \text{if }n=2^k,k>1\end{array}$$

证明

数学归纳法是一种证明与自然数相关的命题的方法.

首先我们要证明 基例(Base Case) ³:

由递归定义, 得 $$T(2)=2$$ 代入解: $$T(2)=2log2=2$$ 二者一致, 故基例成立.

然后我们证明 归纳步骤(Inductive Step):

对于 $n=2^k$, 通过解有 $T(2^k)=2^k\log 2^k=k\times 2^k$(归纳假设).

接着通过递归定义, 假令 $n=2^{k+1}$: $$T(2^{k+1})=2T\left(\frac{2^{k+1}}{2}\right)+2^{k+1}=2T(2^k)+2^{k+1}$$

接着通过归纳假设变形: $$T(2^{k+1})=(k+1)2^{k+1}$$ 这与原有的归纳假设不冲突, 因此归纳假设成立.

从而证明了递归式的解为$T(n)=n\log n$.

1. 关于对数相关知识, 请参考幂与对数. ↩

2. 因而, 《算法导论》中也使用过$\lg$来代替$\log$. (其实《算法导论》很多情况令$\lg$等效于${\log }_2$, 而非${\log }_{10}$, 本书不破坏$\lg$的原有定义) ↩

3. 在该证明中类似于我们之前的 基线条件(Base Case). ↩