分治法

分治法的核心原则

分治法包含三个基本步骤：

分解（Divide）：将原问题分解为若干个同类型的更小的子问题。
解决（Conquer）：递归地解决每个子问题，直到达到可以简单解决的基础情况（基线条件）。
合并（Combine）：将子问题的解合并起来，从而得到原问题的解。

为了应用分治法，问题应满足以下特点：

问题可分解：原问题可以分解成原问题的更小实例。
子问题独立：每个子问题都可以独立求解，而不会影响其他子问题。
解可合并：子问题的解能够被有效地合并，以构成原问题的解。

资料来源：docs/chapter_divide_and_conquer/binary_search_recur.md9-20 docs/chapter_divide_and_conquer/build_binary_tree_problem.md9-16

分治法与其他算法方法有相似之处，但也有关键区别：

算法范式	子问题处理	最优性	典型复杂度
分治法	独立的子问题	找到精确解	通常为 O(n log n)
动态规划	带有记忆化的重叠子问题	找到最优解	通常为 O(n²)
回溯	通过剪枝探索解空间	找到所有有效的解	通常为 O(2ⁿ)

虽然这三种方法都涉及分解问题，但分治法侧重于独立的子问题，而动态规划处理重叠子问题。回溯法则使用试错法探索整个解空间。

资料来源：docs/chapter_dynamic_programming/intro_to_dynamic_programming.md4-6 docs/chapter_backtracking/backtracking_algorithm.md3-5 docs/chapter_dynamic_programming/dp_problem_features.md3-7

分治法的经典示例

二分搜索

二分查找使用分治法在一个已排序的数组中高效地查找目标元素。

分解：将目标与中间元素进行比较，并排除一半的数组。
解决：递归地在剩余的一半中搜索，直到找到目标或确定它不存在。
合并：不需要明确的合并步骤，因为找到元素本身就解决了问题。

使用分治法实现二分查找

资料来源：docs/chapter_divide_and_conquer/binary_search_recur.md21-45

从遍历构建二叉树

给定二叉树的前序遍历和中序遍历，我们可以使用分治法来重建该树。

分解:
- 从前序遍历（第一个元素）中识别根节点。
- 在中序遍历中找到根节点的位置，以确定左子树和右子树。
- 将两个遍历分别分割成对应于左子树和右子树的部分。
解决：使用各自的遍历部分递归地构建左子树和右子树。
合并：将子树连接到根节点，形成完整的树。

从遍历构建二叉树的实现

资料来源：docs/chapter_divide_and_conquer/build_binary_tree_problem.md16-38 docs/chapter_divide_and_conquer/build_binary_tree_problem.md52-64

汉诺塔

汉诺塔问题清晰地展示了分治法的原理。

分解：将移动 n 个盘子的问题分解为：
- 将 n-1 个盘子从源柱移到辅助柱
- 将最大的盘子从源柱移到目标柱
- 将 n-1 个盘子从辅助柱移到目标柱
解决：递归地解决移动 n-1 个盘子的子问题。
合并：按顺序执行这些步骤即可解决整个问题。

解决汉诺塔问题的实现

资料来源：docs/chapter_divide_and_conquer/hanota_problem.md19-91

时间和空间复杂度分析

分治算法的时间复杂度通常遵循以下递推关系：

$$T(n) = a \cdot T(n/b) + O(n^d)$$

其中

$a$ 是子问题的数量
$n/b$ 是每个子问题的大小
$O(n^d)$ 是分解和合并的成本

这将导致以下时间复杂度：

如果 $a < b^d$：$O(n^d)$
如果 $a = b^d$：$O(n^d \log n)$
如果 $a > b^d$：$O(n^{\log_b a})$

示例复杂度分析

二分查找：$T(n) = T(n/2) + O(1)$ → $O(\log n)$
构建二叉树：$O(n)$，其中 n 是节点数
汉诺塔：$T(n) = 2T(n-1) + O(1)$ → $O(2^n)$

资料来源：docs/chapter_divide_and_conquer/binary_search_recur.md39-45 docs/chapter_divide_and_conquer/build_binary_tree_problem.md97-99 docs/chapter_divide_and_conquer/hanota_problem.md89-91

实现模式

分治算法通常遵循这种递归实现模式：

function divideAndConquer(problem):
    // Base case
    if problem is small enough:
        return solve(problem) directly
    
    // Divide step
    divide problem into subproblems
    
    // Conquer step
    for each subproblem:
        solve recursively
    
    // Combine step
    return combined results

成功实现分治法的关键方面包括：

正确定义基线条件（Base Cases）
高效地分解问题
正确地合并子问题的解

资料来源：docs/chapter_divide_and_conquer/binary_search_recur.md39-45 docs/chapter_divide_and_conquer/build_binary_tree_problem.md57-63 docs/chapter_divide_and_conquer/hanota_problem.md83-88

总结

分治算法是一种强大的算法范式，它通过将问题分解为更小、可管理的子问题来解决问题。当满足以下条件时，它特别有效：

子问题彼此独立
问题规模在每次分解后都能显著减小
子问题的解能够被有效地合并

这种方法催生了许多高效的算法，包括二分查找、归并排序、快速排序，以及解决汉诺塔等复杂问题的算法。理解何时以及如何应用分治法对于算法设计和优化至关重要。

分治法