分治法

前言

这学期学算法设计与分析，因为在家看直播学效率不如在学校高，故在此记录学习过程中遇到的问题和学到的东西，希望能帮助到别人也能帮助自己更加牢固的掌握知识。

---

分治法是什么

分治法，顾名思义就是分而治之，即将一个大问题分解为若干个不相交的同类型的小问题,分别解决每个小问题(因为是同类型的问题,所以可以递归地求解;当问题规模足够小时,就直接求解),然后将得到的结果重新组合成为大问题的解。

简而言之，分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

---

使用分治法解决问题的步骤

(1) 分: 将原问题分解为同类型不相交的若干子问题
(2) 治: 递归地解决这些子问题;当规模足够小时,可以直接求解
(3) 合: 将子问题的解合并为原问题的解

---

分治法适用情况

如果原问题可以分割成k个子问题，1<k<=n，且这些子问题均可解并且利用这些子问题的解求出原问题的解，那么分治方法就是可行的。
例如，二分查找就是可以用分治法的典型问题。第一步 分: 如果中位元素不是要找的,将n个元素的序列分成两个含有n/2个元素的子序列。第二步 治: 递归查找其中⼀一个子序列直到序列只有一个元素。第三步 合: 返回查找结果。

---

分治法的复杂性分析

这里以归并排序为例，使用分治法时归并排序的时间复杂度如下 image

那么如何算出T(n)呢，这里我推荐两种方法

法一：递归树法 image

法二：数学运算法

image image

---

分治法主定理

image

打扰了，上面那张图是我们老师上课的时候给我们放的，翻译成人话就是

image

还是打扰了，其实简单理解一下就是

image

有了主定理，我们进行时间复杂度的求解只需把中心放在T(n)表达式的求解上

---

总结

学习分治法，你应该知道其使用的条件，如何写出T(n)表达式，如何解出T(n)，掌握分治法主定理。

如果需要更多实例去理解，可以自行百度搜索，根据例子去理解动手，是最有效的方法。