前言
这学期学算法设计与分析，因为在家看直播学效率不如在学校高，故在此记录学习过程中遇到的问题和学到的东西，希望能帮助到别人也能帮助自己更加牢固的掌握知识。
分治法是什么
分治法，顾名思义就是分而治之，即将一个大问题分解为若干个不相交的同类型的小问题,分别解决每个小问题(因为是同类型的问题,所以可以递归地求解;当问题规模足够小时,就直接求解),然后将得到的结果重新组合成为大问题的解。
简而言之，分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
使用分治法解决问题的步骤
(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)，掌握分治法主定理。
如果需要更多实例去理解，可以自行百度搜索，根据例子去理解动手，是最有效的方法。
网友评论