0020. 分治算法

• 1. 🎯 本节内容
• 2. 🫧 评价
• 3. 🤔 分治算法是什么？
• 4. 🤔 分治算法的三个步骤是什么？
• 5. 🤔 分治算法的特点是什么？
• 6. 🤔 经典的分治算法例子有哪些？
  • 6.1. 归并排序（Merge Sort）
  • 6.2. 快速排序（Quick Sort）
  • 6.3. 二分查找（Binary Search）
• 7. 🤔 分治算法的时间复杂度如何分析？
• 8. 🤔 LeetCode 上对应的算法题有哪些？
• 9. 🔗 引用

1. 🎯 本节内容

• 分治算法简介

2. 🫧 评价

记住一句话 👉 分治算法的核心是：“将大问题分解为独立的子问题，分别求解后合并结果。”

• 三个关键步骤：分解（Divide）、求解（Conquer）、合并（Combine）
• 经典应用：归并排序、快速排序、二分查找
• 面试常考点：能否并行处理（子问题独立）、递归树的时间复杂度分析

3. 🤔 分治算法是什么？

分治法（英语：Divide and conquer）是建基于多项分支递归的一种很重要的算法范型。

字面上的解释是"分而治之"，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

4. 🤔 分治算法的三个步骤是什么？

1. 分解（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题
2. 求解（Conquer）：递归地求解各个子问题。若子问题足够小，则直接求解
3. 合并（Combine）：将各个子问题的解合并为原问题的解

5. 🤔 分治算法的特点是什么？

1. 问题可分解：原问题可以分解为若干个规模较小的相同问题
2. 子问题独立：子问题之间相互独立，不重叠（这是与动态规划的主要区别）
3. 递归求解：子问题的解可以递归求解
4. 合并结果：可以将子问题的解合并为原问题的解

6. 🤔 经典的分治算法例子有哪些？

6.1. 归并排序（Merge Sort）

• 分解：将数组从中间分成两半
• 求解：递归地对两个子数组排序
• 合并：将两个有序子数组合并成一个有序数组
• 时间复杂度：$O(n\log n)$

6.2. 快速排序（Quick Sort）

• 分解：选择一个基准元素，将数组分为小于和大于基准的两部分
• 求解：递归地对两部分排序
• 合并：因为是原地排序，不需要额外合并步骤
• 时间复杂度：平均 $O(n\log n)$，最坏 $O(n^2)$

6.3. 二分查找（Binary Search）

• 分解：将搜索区间一分为二
• 求解：在包含目标的那一半继续查找
• 合并：直接返回找到的结果
• 时间复杂度：$O(\log n)$

7. 🤔 分治算法的时间复杂度如何分析？

分治算法的时间复杂度通常使用主定理（Master Theorem）来分析。

对于递归关系式：$T(n)=aT(\frac{n}{b})+f(n)$

其中：

• $a$：子问题的个数
• $\frac{n}{b}$：每个子问题的规模
• $f(n)$：分解和合并的时间

典型例子：

• 归并排序：$T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$
• 二分查找：$T(n)=T(\frac{n}{2})+O(1)=O(\log n)$

8. 🤔 LeetCode 上对应的算法题有哪些？

• 912. 排序数组 - 中等 - 可用归并排序或快速排序实现
• 169. 多数元素 - 简单 - 分治法找多数元素
• 53. 最大子数组和 - 中等 - 经典分治问题，也可用动态规划

9. 🔗 引用

• LeetCode 912. 排序数组
• LeetCode 169. 多数元素
• LeetCode 53. 最大子数组和