学习笔记 数据结构与算法

分治算法

分解-解决-合并的问题求解策略

一、算法概述

分治算法（Divide and Conquer）是计算机科学中最基本、最强大的算法设计范式之一。其核心思想是将一个难以直接解决的大问题，分解为若干个规模较小、相互独立且与原问题形式相同的子问题，递归地解决这些子问题，然后将子问题的解合并得到原问题的解。

分治思想源于人类处理复杂问题的自然直觉：逐层分解，逐个击破。从古代的"分而治之"军事策略，到现代软件工程中的模块化设计，无不体现这一哲学。在算法领域，分治不仅是解决问题的工具，更是一种思维框架，帮助我们以递归的视角审视问题结构。

分治的三大优势

  • 结构清晰： 将复杂问题简化为已知问题的求解，代码递归结构天然反映问题分解层次
  • 效率突破： 许多分治算法能将暴力枚举的指数级复杂度降为多项式级甚至对数级（如归并排序 O(n log n) 超越了冒泡排序 O(n^2)）
  • 并行潜力： 子问题相互独立，天然适合并行计算和多核处理（MapReduce 的核心就是分治思想）

分治算法的本质是递归思维：不相信自己能解决整个问题，但相信自己能解决更小的问题。这种"信任跳跃"是递归编程的精髓所在。

二、核心三步骤：分解-解决-合并

所有分治算法都遵循三个严格定义的步骤，这是分治范式的统一框架：

  1. 分解（Divide）： 将原问题分解为若干个规模更小的子问题。子问题应与原问题形式相同，最好规模大致相等（平衡分治通常效率最优）。
  2. 解决（Conquer）： 递归地解决每个子问题。当子问题规模足够小（达到基准情形 base case）时，直接求解，不再递归。
  3. 合并（Combine）： 将所有子问题的解合并为原问题的解。合并策略是区分不同分治算法的关键——归并排序的合并是线性归并，快速排序的合并是原地重组，最大子数组和的合并是跨中点扫描。

以下代码展示了分治算法的通用骨架：

Python
# 分治算法通用骨架 def divide_and_conquer(problem): # 基准情形：问题足够小，直接求解 if is_trivial(problem): return solve_directly(problem) # Step 1: 分解为子问题 subproblems = divide_into_subproblems(problem) # Step 2: 递归解决每个子问题 sub_solutions = [] for sub in subproblems: sub_solutions.append(divide_and_conquer(sub)) # Step 3: 合并子问题的解 result = combine_sub_solutions(sub_solutions) return result

实现分治算法时需要特别注意三点：基准情形（base case）必须正确且可达，确保递归能终止；子问题应相互独立，避免重叠子问题导致指数级重复计算；合并步骤的复杂度往往是算法效率的关键瓶颈。

三、分治 vs 动态规划

分治算法与动态规划（Dynamic Programming）都使用递归分解问题的策略，但二者有本质区别。理解这一区别对正确应用两种范式至关重要。

对比维度 分治算法 动态规划
子问题关系 相互独立（不重叠） 相互重叠（共享子问题）
求解方式 自顶向下递归，无记忆化 自底向上递推，或自顶向下+记忆化
典型代表 归并排序、快速排序、最近点对 斐波那契数列、背包问题、最短路径
存储开销 通常只需递归栈空间 需要额外 DP 表存储子问题解
效率关键 合并步骤的复杂度 状态转移方程的设计

判断标准

当一个问题分解为子问题后，如果子问题之间不重叠（即每个子问题只出现一次），适合用分治；如果子问题大量重叠（同一子问题被反复求解），适合用动态规划。例如，计算斐波那契数列如果使用朴素分治递归，会导致指数级重复计算，而动态规划将其降为 O(n)。

Python - 对比演示：斐波那契数列
# 分治方式（朴素递归）—— 存在大量重叠子问题，效率低下 def fib_divide_conquer(n): if n <= 1: return n # 子问题 fib(n-1) 和 fib(n-2) 大量重叠 return fib_divide_conquer(n - 1) + fib_divide_conquer(n - 2) # 时间复杂度: O(2^n) # 动态规划方式（自底向上）—— 消除重复计算 def fib_dp(n): if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] # 时间复杂度: O(n)

四、主定理（Master Theorem）

主定理是分析分治算法时间复杂度的核心工具。它给出了求解形如 T(n) = aT(n/b) + f(n) 递推关系式的直接公式，其中 a >= 1 是子问题个数，b > 1 是规模缩减因子，f(n) 是分解和合并的代价。

主定理标准形式

设 T(n) = aT(n/b) + f(n)，其中 a >= 1，b > 1，f(n) 为渐近正函数。则 T(n) 的渐近复杂度由 f(n) 与 n^(log_b a) 的比较决定：

情形一： 若 f(n) = O(n^(log_b a - ε))，则 T(n) = Θ(n^(log_b a))
情形二： 若 f(n) = Θ(n^(log_b a))，则 T(n) = Θ(n^(log_b a) · log n)
情形三： 若 f(n) = Ω(n^(log_b a + ε))，则 T(n) = Θ(f(n))

三种情形的详细解读

情形一：叶子主导

当 f(n) 的增长慢于 n^(log_b a) 时，算法的总代价由叶子节点的数量主导。这意味着递归分解的开销远小于子问题的求解开销。

经典案例： 归并排序的递推式为 T(n) = 2T(n/2) + Θ(n)。这里 a=2, b=2, log_b a = 1, f(n)=Θ(n) = Θ(n^1)。这不属于情形一（因为 f(n) 不是 O(n^(1-ε))），实际属于情形二。

情形一的真正案例： T(n) = 2T(n/2) + Θ(√n)。log_b a = 1, f(n)=√n = O(n^(1-0.5)), 所以 T(n) = Θ(n)。

情形二：均衡分布

当 f(n) 与 n^(log_b a) 同阶时，每一层的代价大致相等，总代价为叶子层代价乘以树高 log n。

经典案例： 归并排序 T(n) = 2T(n/2) + Θ(n)。a=2, b=2, log_b a = 1, f(n)=Θ(n) = Θ(n^1)，属于情形二，因此 T(n) = Θ(n log n)。

情形三：根节点主导

当 f(n) 的增长快于 n^(log_b a) 时，算法的总代价由根节点的分解合并操作主导，递归深度的影响被压制。

经典案例： T(n) = 2T(n/2) + Θ(n^2)。log_b a = 1, f(n)=n^2 = Ω(n^(1+1)), 且满足正则条件 2f(n/2) <= c·f(n)，属于情形三，T(n) = Θ(n^2)。

重要提示：主定理的局限性

主定理不适用于所有递推式。当 f(n) 不是多项式可比的（如 f(n) = n log n 与 n^(log_b a) 的比较落在间隙中），或递推式非标准形式（如 T(n) = √n·T(√n) + n），需要借助递归树法或代入法求解。

五、经典排序：归并排序

归并排序是分治算法最经典的代表。它将数组递归地分成两半，分别排序后合并两个有序数组。归并排序的时间复杂度稳定在 O(n log n)，且是稳定排序（相等元素的相对顺序不变），但需要 O(n) 额外空间。

Python - 归并排序实现
def merge_sort(arr): # 基准情形：空或只有一个元素，已经有序 if len(arr) <= 1: return arr # Step 1: 分解 —— 从中间分割数组 mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] # Step 2: 递归排序两半 sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) # Step 3: 合并两个有序数组 return merge(sorted_left, sorted_right) def merge(left, right): result = [] i = j = 0 # 双指针合并：每次取两个数组中较小的元素 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # 处理剩余元素 result.extend(left[i:]) result.extend(right[j:]) return result

归并排序的递推分析

T(n) = 2T(n/2) + Θ(n)：a=2, b=2, log_b a = 1, f(n)=Θ(n)。属于主定理情形二，得出 T(n) = Θ(n log n)。归并排序的 n log n 是最优比较排序的下界，因此归并排序在渐近意义下已经是最优的。

六、经典排序：快速排序

快速排序是另一种基于分治的排序算法，但与归并排序不同，它的核心工作发生在分解阶段而非合并阶段。快速排序选择一个"基准"（pivot），将数组划分为小于基准和大于基准两部分，然后递归排序这两部分。快速排序是原地排序（不需要额外数组），但不稳定。

Python - 快速排序实现
def quick_sort(arr, low, high): if low < high: # 分区操作：返回基准元素的最终位置 pivot_index = partition(arr, low, high) # 递归排序基准左右两侧 quick_sort(arr, low, pivot_index - 1) quick_sort(arr, pivot_index + 1, high) def partition(arr, low, high): # 选择最右侧元素作为基准（可优化为随机选择） pivot = arr[high] i = low - 1 # i 指向"小于区"的末尾 for j in range(low, high): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] # 将小于基准的元素换到左边 # 将基准放到正确位置（i+1 处） arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1

复杂度分析：最优 vs 最坏

最优情况（均匀划分）： 每次分区恰好将数组分为两半，递推式 T(n) = 2T(n/2) + Θ(n)，时间复杂度 Θ(n log n)。

最坏情况（极度不平衡）： 每次分区只划分出一个元素，递推式 T(n) = T(n-1) + Θ(n)，时间复杂度 Θ(n^2)。当数组已经有序时发生（如果选择固定位置基准）。

优化策略： 随机选择基准、三数取中法、切换到插入排序（小规模子数组）。实践中快速排序只需 Θ(log n) 的递归栈空间。

七、二分搜索与快速幂

7.1 二分搜索

二分搜索是最简单的分治算法之一：在一个有序数组中查找目标值，每次将搜索范围缩小一半。递推式 T(n) = T(n/2) + O(1)，属于主定理情形二，T(n) = O(log n)。

Python - 二分搜索
def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 # 防止整数溢出 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 # 在右半部分查找 else: right = mid - 1 # 在左半部分查找 return -1 # 未找到

7.2 快速幂

快速幂（Fast Power / Binary Exponentiation）利用分治思想在 O(log n) 时间内计算 a^n。核心思想是：n 为偶数时，a^n = (a^(n/2))^2；n 为奇数时，a^n = a · a^(n-1)。递推式 T(n) = T(n/2) + O(1)，复杂度 O(log n)。

Python - 快速幂（递归与迭代）
# 递归版快速幂 def fast_pow_recursive(a, n): if n == 0: return 1 if n == 1: return a half = fast_pow_recursive(a, n // 2) if n % 2 == 0: return half * half else: return half * half * a # 迭代版快速幂（更高效，无递归开销） def fast_pow_iterative(a, n): result = 1 base = a exp = n while exp > 0: if exp & 1: # 当前最低位为 1 result *= base base *= base # base 平方 exp >>= 1 # 右移一位 return result

快速幂的应用

快速幂广泛应用于：密码学中的 RSA 加密（模幂运算）、矩阵快速幂（求解线性递推数列，如斐波那契数列 O(log n) 求解）、概率论中的分布计算等。矩阵快速幂将矩阵视为"base"，同样使用二进制分解思想。

八、最大子数组和

问题定义： 给定整数数组 nums，找出一个具有最大和的连续子数组（子数组要求连续），返回其最大和。例如，输入 [-2,1,-3,4,-1,2,1,-5,4]，最大子数组为 [4,-1,2,1]，和为 6。

分治解法将数组从中间分为两半，最大子数组和可能出现在三种位置：

  1. 完全在左半部分（递归求解）
  2. 完全在右半部分（递归求解）
  3. 跨越中点（从中间向两侧扫描合并）
Python - 最大子数组和的分解解法
def max_subarray_sum(nums, left, right): # 基准情形：只有一个元素 if left == right: return nums[left] mid = (left + right) // 2 # 递归求解左右两半的最大子数组和 left_max = max_subarray_sum(nums, left, mid) right_max = max_subarray_sum(nums, mid + 1, right) # 求解跨越中点的最大子数组和 # 从中点向左扩展，找最大和 left_sum = float('-inf') total = 0 for i in range(mid, left - 1, -1): total += nums[i] if total > left_sum: left_sum = total # 从中点向右扩展，找最大和 right_sum = float('-inf') total = 0 for i in range(mid + 1, right + 1): total += nums[i] if total > right_sum: right_sum = total # 跨越中点的最大和 = 左半最大后缀 + 右半最大前缀 cross_max = left_sum + right_sum # 返回三者中的最大值 return max(left_max, right_max, cross_max) # 调用方式：max_subarray_sum(nums, 0, len(nums) - 1)

复杂度分析

递推式 T(n) = 2T(n/2) + O(n)（合并需要线性扫描中点两侧），属于主定理情形二，时间复杂度为 O(n log n)。需要注意，最大子数组和存在更优的 Kadane 算法，时间复杂度 O(n)，空间复杂度 O(1)，但分治版本展示了分治思想在非排序问题中的应用。

九、大整数乘法 - Karatsuba 算法

当整数位数很大时（如 1000 位），传统小学乘法的时间复杂度为 O(n^2)。Karatsuba 算法（1960 年）利用分治思想将复杂度降至 O(n^(log_2 3)) ≈ O(n^1.585)。

核心思想： 将两个 n 位数 x 和 y 各分成高低两半：x = a·10^(n/2) + b, y = c·10^(n/2) + d。则 x·y 可以通过三个乘法而非四个乘法计算：

ac = a·c
bd = b·d
(a+b)(c+d) = ac + ad + bc + bd
x·y = ac·10^n + ( (a+b)(c+d) - ac - bd ) · 10^(n/2) + bd

这样只需要 3 次乘法而非 4 次，递推式变为 T(n) = 3T(n/2) + O(n)，依据主定理情形一（f(n)=n, n^(log_2 3) ≈ n^1.585），得 T(n) = O(n^(log_2 3))。

Python - Karatsuba 大整数乘法
def karatsuba(x, y): # 基准情形：小整数直接相乘 if x < 10 or y < 10: return x * y # 计算位数，取较大者的半数 n = max(len(str(x)), len(str(y))) m = n // 2 # 分解为高低两半 power = 10 ** m a = x // power b = x % power c = y // power d = y % power # 三次乘法（而非四次） ac = karatsuba(a, c) bd = karatsuba(b, d) ab_cd = karatsuba(a + b, c + d) # 合并：ac·10^(2m) + (ab_cd - ac - bd)·10^m + bd return ac * (10 ** (2 * m)) + (ab_cd - ac - bd) * (10 ** m) + bd

进一步优化：Toom-Cook 算法

Karatsuba 算法将大整数乘法从 O(n^2) 降到 O(n^1.585)。更一般的 Toom-Cook 算法将每个数分成 k 段，使用 2k-1 次乘法，复杂度为 O(n^(log(2k-1)/log k))。当 k=3 时，复杂度约为 O(n^1.465)。现代密码学库（如 GMP）混合使用多种算法，根据输入规模自动选择最优策略。

十、Strassen 矩阵乘法

矩阵乘法是科学计算的核心操作。传统矩阵乘法（三层循环）的时间复杂度为 O(n^3)。Strassen 在 1969 年提出了第一个突破 O(n^3) 的矩阵乘法算法，利用分治将复杂度降至 O(n^(log_2 7)) ≈ O(n^2.807)。

核心思想： 将 n×n 矩阵分为四个 n/2 × n/2 的子矩阵，通过 7 次乘法（而非 8 次）和若干次加减法完成乘法。七个递归乘法如下：

M1 = (A11 + A22) · (B11 + B22)
M2 = (A21 + A22) · B11
M3 = A11 · (B12 - B22)
M4 = A22 · (B21 - B11)
M5 = (A11 + A12) · B22
M6 = (A21 - A11) · (B11 + B12)
M7 = (A12 - A22) · (B21 + B22)
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
Python - Strassen 矩阵乘法（框架）
import numpy as np def strassen(A, B): n = A.shape[0] # 基准情形：小矩阵用传统乘法 if n <= 64: return A @ B # 确保 n 为偶数，必要时补零 if n % 2 != 0: A = np.pad(A, ((0,1),(0,1)), mode='constant') B = np.pad(B, ((0,1),(0,1)), mode='constant') n += 1 m = n // 2 # 分解为四个子矩阵 A11, A12, A21, A22 = A[:m,:m], A[:m,m:], A[m:,:m], A[m:,m:] B11, B12, B21, B22 = B[:m,:m], B[:m,m:], B[m:,:m], B[m:,m:] # 七次乘法（递归） M1 = strassen(A11 + A22, B11 + B22) M2 = strassen(A21 + A22, B11) M3 = strassen(A11, B12 - B22) M4 = strassen(A22, B21 - B11) M5 = strassen(A11 + A12, B22) M6 = strassen(A21 - A11, B11 + B12) M7 = strassen(A12 - A22, B21 + B22) # 合并结果 C11 = M1 + M4 - M5 + M7 C12 = M3 + M5 C21 = M2 + M4 C22 = M1 - M2 + M3 + M6 # 组合为完整矩阵 C = np.vstack([ np.hstack([C11, C12]), np.hstack([C21, C22]) ]) return C[:n,:n] # 去除补零部分

理论与实践

递推式 T(n) = 7T(n/2) + O(n^2)，a=7, b=2, log_b a = log_2 7 ≈ 2.807, f(n)=O(n^2) = O(n^(2.807-ε))，属于情形一，T(n) = Θ(n^(log_2 7)) = Θ(n^2.807)。需要注意的是，Strassen 算法的常数因子较大，且数值稳定性不如传统乘法。实践中通常在矩阵规模大于某个阈值（如 128×128）时才切换到 Strassen。后续的 Coppersmith-Winograd 算法（O(n^2.376)）及其变体虽然理论更优，但常数巨大，实际很少使用。

十一、计算几何：最近点对

问题定义： 给定平面上的 n 个点，找出欧几里得距离最近的 pair。暴力方法 O(n^2) 检查所有点对。分治方法在 O(n log n) 内解决。

分治策略：

  1. 将所有点按 x 坐标排序（预处理，不计入递归复杂度）
  2. 按 x 中位数将点集分为左右两半，递归求左右各自的最小距离 d_left 和 d_right，令 d = min(d_left, d_right)
  3. 关键步骤：合并时只需要检查跨越中线的点对。只考虑 x 坐标在 [mid_x - d, mid_x + d] 区间内的点，将这些点按 y 坐标排序后，每个点最多只需要和后续 7 个点比较距离
Python - 最近点对的分治解法
import math def closest_pair(points): # 预处理：按 x 坐标排序 points_sorted = sorted(points, key=lambda p: p[0]) return _closest_pair(points_sorted) def _closest_pair(points): n = len(points) # 基准情形：暴力求解小规模 if n <= 3: min_dist = float('inf') for i in range(n): for j in range(i + 1, n): d = dist(points[i], points[j]) if d < min_dist: min_dist = d return min_dist # 按 x 中位数分割 mid = n // 2 mid_x = points[mid][0] left_half = points[:mid] right_half = points[mid:] # 递归求解左右两半 d_left = _closest_pair(left_half) d_right = _closest_pair(right_half) d = min(d_left, d_right) # 关键：筛选出距离中线 d 以内的点（按 y 排序） strip = [p for p in points if abs(p[0] - mid_x) < d] strip.sort(key=lambda p: p[1]) # 在 strip 中检查每个点与后续点的距离（最多 7 个） for i in range(len(strip)): for j in range(i + 1, min(i + 7, len(strip))): if strip[j][1] - strip[i][1] >= d: break # y 坐标差已超过 d，无需继续 d = min(d, dist(strip[i], strip[j])) return d def dist(p1, p2): return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

分治策略为什么高效？

如果不利用分治的剪枝策略，合并步骤需要 O(n^2) 的时间。但借助"中线 ± d"的带状区域限制和 y 坐标排序后的至多 7 次比较，合并步骤降为 O(n)。递推式 T(n) = 2T(n/2) + O(n)，由主定理得 T(n) = O(n log n)。若在合并时对 strip 按 y 排序，考虑到排序开销，整体复杂度为 O(n log^2 n)，但可以通过预排序和归并技巧优化到 O(n log n)。

十二、时间复杂度分析汇总

算法 递推关系 主定理情形 时间复杂度
二分搜索 T(n) = T(n/2) + O(1) 情形二 O(log n)
快速幂 T(n) = T(n/2) + O(1) 情形二 O(log n)
归并排序 T(n) = 2T(n/2) + O(n) 情形二 O(n log n)
快速排序（平均） T(n) = 2T(n/2) + O(n) 情形二 O(n log n)
最大子数组和 T(n) = 2T(n/2) + O(n) 情形二 O(n log n)
最近点对 T(n) = 2T(n/2) + O(n) 情形二 O(n log n)
Karatsuba 乘法 T(n) = 3T(n/2) + O(n) 情形一 O(n^(log_2 3))
Strassen 矩阵乘 T(n) = 7T(n/2) + O(n^2) 情形一 O(n^(log_2 7))
快速排序（最坏） T(n) = T(n-1) + O(n) 不适用 O(n^2)

主定理揭示了分治算法复杂度的本质规律：子问题个数 a 和规模缩减因子 b 共同决定了递推树的"分支因子"log_b a，而 f(n) 则决定了每层的合并代价。算法的整体效率取决于这两者的相对大小。

分治算法的适用场景判断

一个问题是否适合用分治算法求解，可以从以下角度判断：

  1. 可分解性： 问题能否自然地划分为结构相同、规模更小的子问题？
  2. 子问题独立性： 子问题之间是否没有重叠（即每个子问题的解不依赖其他子问题的中间结果）？
  3. 可合并性： 子问题的解能否高效地合并为原问题的解？合并步骤的复杂度直接影响整体效率。
  4. 平衡性： 是否能将问题均匀地划分为规模大致相等的子问题？不平衡的分治可能导致最坏情况退化。
  5. 基准情形： 能否定义合理的基准情形（问题规模足够小时可以直接求解）？

十三、核心要点总结

分治算法知识框架

  • 核心原则： 分治算法遵循"分解-解决-合并"三步骤范式。分解将大问题化为小问题，解决递归求解子问题，合并将子问题解组装为原问题解。
  • 与 DP 的区别： 分治要求子问题相互独立；动态规划处理重叠子问题并利用记忆化避免重复计算。这是选择算法范式的关键判断标准。
  • 主定理： T(n) = aT(n/b) + f(n) 的递推关系可以通过主定理快速求解。三种情形分别对应叶子主导、均衡分布和根节点主导三种场景。
  • 归并与快排： 两者的核心区别在于工作发生的阶段——归并排序的合并步骤是核心（合并有序数组），快速排序的分区步骤是核心（原地划分）。
  • 突破理论下界： Karatsuba 乘法和 Strassen 矩阵乘法展示了分治如何突破直观下界（O(n^2) 和 O(n^3)），通过"减少子问题个数"（4→3, 8→7）来降低复杂度指数。
  • 最近点对剪枝： 利用"中线 ± d"的带状区域限制，将合并步骤从 O(n^2) 降为 O(n)，每个点只需与后续至多 7 个点比较，这是分治剪枝的经典范例。
  • 工程实践： 实际应用中常将分治与暴力方法混合——当问题规模小于阈值时切换到直接求解（如 Strassen 切换到传统矩阵乘法），以减少递归开销和常数因子。

十四、进一步思考

分治算法的思想远不止于上述具体算法。在更广阔的计算机科学领域中，分治是一种元方法论：

分治思想的跨领域应用

  • 并行计算： MapReduce 编程模型本质上是分布式分治——Map 阶段分解任务，Reduce 阶段合并结果。Google 的整个大数据基础设施都建立在这一思想上。
  • FFT（快速傅里叶变换）： Cooley-Tukey 算法利用分治将 DFT 从 O(n^2) 优化到 O(n log n)，是数字信号处理和图像处理的基石。
  • 线段树与树状数组： 将区间分解为若干不相交的标准区间，实现 O(log n) 的区间查询和更新。
  • CDQ 分治： 一种特殊的分治技巧，用于解决三维偏序等复杂问题，将动态问题转化为静态问题处理。
  • 算法设计之外： 分治思维可用于系统设计中的模块划分、项目管理中的任务分解、甚至日常生活中的问题解决——将复杂问题拆解为可管理的小块逐一攻克。

计算机科学中的所有问题都可以通过添加一层抽象来解决——分治正是通过"分解"创建抽象层，通过"合并"整合抽象层。理解分治，不仅是理解一类算法，更是理解计算思维本身。