分治算法基础

快速概览

分治算法是处理大规模数据的核心范式：把大问题分解成小问题，分别解决后再合并。这一页从经典排序算法出发，建立分治的直觉。

• 先理解归并排序的分治思想，再看快速排序的随机化策略会更顺。
• 分治思想也体现在系统发育树构建、多重序列比对等生物信息学任务中。

前置知识

• 算法与复杂度
• 随机化算法
• 动态规划基础

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

是什么

分治（divide and conquer）是一种算法设计范式：

1. 分解（Divide）：把原问题分解成多个规模较小的子问题
2. 解决（Conquer）：递归地解决各个子问题
3. 合并（Combine）：把子问题的解合并成原问题的解

适用条件

问题可以分解为相互独立、结构相同的子问题。

典型复杂度

通常满足递推式 $T(n) = aT(n/b) + f(n)$，可用主定理分析。

优势

把指数级问题降为多项式级，充分利用并行计算。

要解决什么生物信息学问题

分治算法在生物信息学中有广泛应用：

• 序列排序：对 reads、k-mers、特征进行排序
• 系统发育树构建：UPGMA、Neighbor-Joining 等距离法
• 多重序列比对：ClustalW 等渐进式比对策略
• 最近点对搜索：在结构生物学中找最近的原子或残基
• 空间索引：KD-tree、R-tree 等用于快速空间查询

核心思想

分治的核心价值在于：

• 降低复杂度：把 $O(2^n)$ 的问题降为 $O(n \log n)$
• 模块化：子问题独立，便于并行化和优化
• 递归结构：代码简洁，逻辑清晰

1. 归并排序（Merge Sort）

归并排序是分治算法的典型应用。

分解

把数组分成两半，递归排序。

合并

合并两个已排序的子数组，保持有序。

时间复杂度

$O(n log n)$ 最坏、平均、最好都相同。

空间复杂度

$O(n)$ 需要额外空间。

稳定性

稳定排序，相等元素的相对顺序不变。

示例

排序数组：[38, 27, 43, 3, 9, 82, 10]

分解过程：

[38, 27, 43, 3, 9, 82, 10]
         ↓
[38, 27, 43]    [3, 9, 82, 10]
     ↓              ↓
[38, 27] [43]   [3, 9] [82, 10]
   ↓       ↓      ↓       ↓
[38] [27] [43] [3] [9] [82] [10]

合并过程：

[27, 38]  [43]   [3, 9]   [10, 82]
    ↓        ↓      ↓        ↓
[27, 38, 43]    [3, 9, 10, 82]
        ↓              ↓
[3, 9, 10, 27, 38, 43, 82]

合并操作

合并两个已排序数组 [2, 5, 8] 和 [1, 3, 4, 7]：

指针 i=0, j=0
比较 2 和 1，取 1，j++
比较 2 和 3，取 2，i++
比较 5 和 3，取 3，j++
比较 5 和 4，取 4，j++
比较 5 和 7，取 5，i++
比较 8 和 7，取 7，j++
比较 8 和 ∅，取 8，i++
结果：[1, 2, 3, 4, 5, 7, 8]

在生物信息学中的应用

• k-mer 排序：组装前对 k-mer 进行排序
• read 排序：按位置、质量或其他特征排序
• 特征排序：机器学习特征工程中的排序操作

2. 快速排序（Quick Sort）

快速排序是另一种分治排序算法，采用分区（partition）策略。

分解

选择一个 pivot，把数组分成小于 pivot 和大于 pivot 两部分。

解决

递归排序两部分。

合并

不需要显式合并，原地完成。

时间复杂度

平均 $O(n log n)$，最坏 $O(n^2)$（已排序且 pivot 选择不当）。

空间复杂度

$O(log n)$ 递归栈空间。

示例

排序数组：[38, 27, 43, 3, 9, 82, 10]

选择 pivot=38（第一个元素）：

分区后：[27, 3, 9, 10]（小于38）[38]（pivot）[43, 82]（大于38）

递归排序：

• 左边 [27, 3, 9, 10] → [3, 9, 10, 27]
• 右边 [43, 82] → [43, 82]

最终结果：[3, 9, 10, 27, 38, 43, 82]

Pivot 选择策略

策略	描述	最坏情况
第一个元素	简单	已排序数组 $O(n^2)$
随机选择	平均性能好	概率极低
三数取中	选择首、中、末的中位数	很难触发最坏
优化策略	小数组用插入排序	实际工程常用

在生物信息学中的应用

• 大规模数据排序：比归并排序更节省内存
• 分区统计：快速找到中位数、分位数
• k-mer 计数优化：某些 k-mer 计数工具使用快速排序变种

3. 最近点对问题（Closest Pair）

给定平面上的 $n$ 个点，找到距离最近的两个点。

朴素算法

枚举所有点对，$O(n^2)$。

分治算法

$O(n log n)$。

核心思想

按 x 坐标分治，递归求解，再合并跨越分界线的点对。

算法步骤

1. 预处理：按 x 坐标排序，$O(n \log n)$
2. 分治：用垂直线把点集分成左右两半
3. 递归：分别求左右两半的最近点对
4. 合并：检查跨越分界线的点对（只需检查带状区域内的点）

示例

点集：(1,2), (3,4), (5,1), (7,3), (9,2)

按 x 排序后，分界线 x=5：

• 左边：(1,2), (3,4), (5,1)
• 右边：(7,3), (9,2)

递归求解：

• 左边最近：(1,2) 和 (3,4)，距离 $\sqrt{8}$
• 右边最近：(7,3) 和 (9,2)，距离 $\sqrt{5}$

合并：检查分界线附近的点对

在生物信息学中的应用

• 蛋白质结构分析：寻找最近的氨基酸残基
• 分子动力学：计算原子间距离
• 空间聚类：基于距离的聚类算法

4. 主定理（Master Theorem）

主定理用于分析形如 $T(n) = aT(n/b) + f(n)$ 的递推式。

形式

$T(n) = aT(n/b) + f(n)$，其中 $a geq 1, b > 1$。

参数含义

a 是子问题数量，b 是子问题规模缩减倍数，f(n) 是分解和合并代价。

三种情况

设 $n^{\log_b a}$ 为临界函数：

1. 情况 1：$f(n) = O(n^{\log_b a - \epsilon})$，$\epsilon > 0$

   • 则 $T(n) = \Theta(n^{\log_b a})$

2. 情况 2：$f(n) = \Theta(n^{\log_b a} \log^k n)$，$k \geq 0$

   • 则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$

3. 情况 3：$f(n) = \Omega(n^{\log_b a + \epsilon})$，$\epsilon > 0$，且满足正则条件

   • 则 $T(n) = \Theta(f(n))$

应用示例

• 归并排序：$T(n) = 2T(n/2) + O(n)$

  • $a=2, b=2, \log_b a = 1$
  • $f(n) = O(n) = O(n^1)$，符合情况 2（$k=0$）
  • $T(n) = \Theta(n \log n)$

• 二分搜索：$T(n) = T(n/2) + O(1)$

  • $a=1, b=2, \log_b a = 0$
  • $f(n) = O(1) = O(n^0)$，符合情况 2（$k=0$）
  • $T(n) = \Theta(\log n)$

5. Hirschberg 算法：空间高效序列比对

为什么需要分治？

标准的动态规划比对算法（如 Needleman-Wunsch）需要 $O(nm)$ 的空间来存储得分矩阵。

• 对于两条长度为 100,000 的序列，矩阵需要 $10^{10}$ 个单元格。
• 假设每个单元格 4 字节，则需要 40 GB 内存。
• 这种”空间爆炸”使得长序列比对在普通机器上变得不可能。

Hirschberg 算法的直觉

Hirschberg 算法的核心发现是：虽然计算最优得分需要整张表，但我们可以在 $O(n)$ 空间内计算出任意一列的得分向量。

1. 分：将序列 $A$ 从中间位置 $mid$ 切开。
2. 求：
   • 从（0,0） 正向计算到 $mid$ 列，得到 $score_{forward}$。
   • 从（n,m） 反向计算到 $mid$ 列，得到 $score_{backward}$。
3. 联：找到一个行索引 $k$，使得 $score_{forward}[k] + score_{backward}[k]$ 最大。这个 $(k, mid)$ 点一定在最优路径上。
4. 治：以 $(k, mid)$ 为界，递归地对比对左上角和右下角的子矩形进行同样的处理。

复杂度分析

• 空间复杂度：$O(m)$，只需要存储当前列和前一列的得分。
• 时间复杂度：$O(nm)$。虽然看起来多做了很多重复计算，但数学证明其总计算量约为标准 DP 的 2 倍。

6. Four Russians 加速

基本思想

Four Russians 方法（也称为 Four Russians’ trick 或 block alignment）通过预计算小方块的最优解来加速 DP。

分块策略

将 DP 表分成 k×k 的小块。

预计算

预先计算所有可能的边界条件下小块的最优路径。

查表

实际计算时，查表而非逐个计算。

时间复杂度

可以降到 O(nm/log n)。

为什么叫 “Four Russians”

这个方法由四位苏联科学家（V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, I. A. Faradzev）在 1970 年提出。

在生物信息学中的应用

• 大规模序列比对：加速基因组比对
• 编辑距离计算：快速计算大量序列对的编辑距离
• 需要权衡：预计算需要额外空间，适合重复计算相同大小方块的场景

7. 在生物信息学中的扩展应用

系统发育树构建：UPGMA

UPGMA（Unweighted Pair Group Method with Arithmetic Mean）使用分治思想：

1. 初始化：每个物种是一个簇
2. 合并：每次合并距离最近的两个簇
3. 更新：重新计算新簇与其他簇的距离
4. 递归：重复直到只剩一个簇

这是自底向上的分治（agglomerative clustering）。

多重序列比对：渐进式比对

ClustalW 等工具使用渐进式策略：

1. 构建距离矩阵：计算所有序列对的距离
2. 构建引导树：用距离矩阵构建系统发育树
3. 渐进比对：按树的顺序，从最相似的序列开始逐步比对

这是基于树的分治策略。

空间数据结构：KD-tree

KD-tree 用于高维空间查询：

1. 构建：交替按不同维度分割空间
2. 查询：递归搜索相关子空间
3. 剪枝：利用几何性质剪枝，避免遍历所有点

应用于蛋白质结构数据库检索、空间聚类等。

算法比较

算法	时间复杂度	空间复杂度	稳定性	适用场景
归并排序	$O(n \log n)$	$O(n)$	稳定	需要稳定排序、外部排序
快速排序	平均 $O(n \log n)$	$O(\log n)$	不稳定	内存受限、平均性能优先
最近点对（分治）	$O(n \log n)$	$O(n)$	-	几何计算、结构分析
最近点对（朴素）	$O(n^2)$	$O(1)$	-	小规模数据、简单实现

常见误区

• 分治总是比朴素算法快：
• 不一定。分治算法：
• 有额外的递归开销
• 可能需要额外空间
• 小规模时，朴素算法可能更快
• 实际中常使用混合策略：小规模用朴素，大规模用分治。

与其他算法的连接

• 动态规划：某些问题既可以用分治也可以用 DP，分治子问题独立，DP 子问题重叠
• 贪心算法：分治递归求解，贪心每步做局部最优
• 随机化算法：快速排序的随机 pivot 选择是分治与随机化的结合

参考资料

• Introduction to Algorithms (CLRS), 第 2、4、33 章
• Algorithm Design, Kleinberg & Tardos
• 系统发育树构建相关教材

动态规划基础

DP 与分治都是处理子问题的范式，核心区别在于子问题是否重叠。

延伸阅读

随机化算法

随机化快速排序是分治与随机化的经典结合。

延伸阅读

系统发育树概览

UPGMA 等距离法本质上是自底向上的分治策略。

延伸阅读

多重序列比对

ClustalW 的渐进式比对是分治思想在序列分析中的典型应用。

延伸阅读

算法与复杂度

分治算法的复杂度分析框架与主定理。

延伸阅读