分治算法，分而治之！
大家好呀，我是帅蛋。
在上一篇文章中我讲了递归算法：
递归是一种很重要的算法，经常在一些高级的算法中应用，比如今天我要讲的分治算法。
分治算法同样也是一种很重要的算法，可能很多同学都听说过分治算法，但是没有系统的了解过。
这篇文章，就让我们来一探究竟。
这篇是我在牛客网连载系列 #帅蛋的数据结构与算法空间#的第 9 篇文章，欢迎大家关注。
也希望大家能够喜欢上帅蛋，多多点赞收藏，记得关注我呀！
什么是分治？
学习分治，得先知道什么是分治。
分治，表面意思就是“分而治之”，洋名儿叫 Divde & Conquer。
正规点的说法是：
分治算法就是将一个大的复杂的问题，拆分成多个相同或者相似的子问题，然后再把子问题拆成更小的子问题，然后再拆成更更小的问题 and so on
直至最后的子问题可以简单求解，那最后问题的解即子问题解的合并。
白话点说就是：
将一个难题，拆成一些规模较小的相同的子问题，各个击破，分而治之。
很多算法用到了分治的思想，比如排序算法中的快排和归并排序，这些等我讲到排序算法的时候再来细聊。
由此可以看出，分治算法真真正正是一种处理问题的思想，这个要区别于递归，递归只是一种编程技巧。
分治算法的过程
分治算法由“分”和“治”两部分组成，但是它主要包括 3 个过程：
- 划分（Divide）
- 求解（Conquer）
- 合并（Combine）
其中：
划分（Divide）：将原问题划分为规模较小的子问题，子问题相互独立，与原问题形式相同。
求解（Conquer）：递归的求解划分之后的子问题。
合并（Combine）：这一步非必须。有些问题涉及合并子问题的解，将子问题的解合并成原问题的解。有的问题则不需要，只是求出子问题的解即可。
分治算法的整个流程可以看下图：
分治算法适用情况
由分治算法的过程可以看出分治算法适用的情况，我的总结是 4 个词：
- 规模大
- 可分解
- 各独立
- 可合并
“规模大”和“可分解”针对原始问题。
即原问题要规模比较大，不易直接解决，但是问题分解成规模较小的相同子问题比较容易解决。
“各独立”和“可合并”针对子问题。
即子问题之间求解是相关独立互不影响，且子问题的解可以合并成原始问题的解。
这四个词中最重要的是“各独立”和“可合并”。
- “各独立”涉及到分治法的效率问题。
如果各个子问题是不独立的，则分治法就需要重复的去解决一些重复的子问题，这样多做了很多不必要的工作。
比如我们很熟悉的斐波那契数列，公式如下：
假设我们要求 f(5)，分治法将其划分为一个个的子问题：
由上图可见，仅仅是求 f(5)，仅仅是只画了 3 层，就已经出现了相同结果的重复计算（比如 f(3) 和 f(2)）。
通过对子问题解的合并，最终的结果毋庸置疑，但是因为各个子问题的不独立，造成了子问题的重复计算，从而分治法求解斐波那契的效率感人...
碰到这种情况，还是动态规划比较合适...
- “可合并”是涉及能否用分治的关键。
如果子问题的解可合并，那就能用分治法。
如果不可合并，单单只是“规模大”和“可分解”，分治就没必要考虑，用贪心或者动态规划才是正理。
设计分治算法
通过之前的了解，其实可以很清楚的发现，用分治算法解决问题的核心，其实就是归纳一个求解的数学公式，然后根据公式设计递归程序。
说白了就是先找找拆分到最小规模问题时怎么解，然后再瞅瞅随着问题规模增大点问题怎么解，最后就是找到递归函数，码出递归代码即可。
分治算法实例
其实在这之前，我已经讲过一个典型的分治算法的应用：二分查找。
可以说二分查找是分治算法中最常用的算法：
二分查找是在一个有序的数组中进行查找吗，每次可以让问题的规模减半。
它思路比较简单：
- 选择一个 mid 将数组分为左右两个集合。
- 判断标志 arr[mid] 是否能与要查找的目标值 target 相等，相等则直接返回。
- 若小于 arr[mid]，则在左半区间继续查找。
- 如大于 arr[mid]，则在右半区继续查找。
- 递归上面的步骤。
def BinarySearch(arr, low, high, target):
if low <= high:
mid = (low + high) / 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return BinarySearch(arr, low, mid - 1, target)
else:
return BinarySearch(arr, mid + 1, high, target)
else:
# 没有找到
return -1 分治算法到这就讲完辣，原理很简单，大家看会了么？
原理搞懂只是迈出学会分治算法的第一步，想要灵活的使用却不是一件容易的事儿，更多的还是要在实战中领悟，在实战中加深对分治算法的理解。
大家只要认真去搞，就一定能掌握分治算法。
我是帅蛋，我们下次见。
❤️ 欢迎关注我，有问题，找帅蛋，我最看不得别人迷茫！
❤️ 如果你觉得有帮助,希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~
还有小小公众号 【编程文青李狗蛋】，聊聊迷茫吹吹牛皮~
- 数据结构与算法作为计算机学生最重要的课程之一，不管是面试或者考研都是重中之重，不应该让这个成为同学们的困扰。 - 站在初学者的角度，用最直白的图解和最易懂的代码，最大可能摒除不同编程语言的带来的干扰，带你彻底搞定数据结构与算法。 - 本专栏适用于任何想要学习数据结构与算法的未来巨巨~
滴滴一面73人在聊
投递华为等公司10个岗位 >