算法之分治

查看sogou和百度的词条解释,真是无言。

分治法的精髓:

分--将问题分解为规模更小的子问题;

治--将这些规模更小的子问题逐个击破;

合--将已解决的子问题合并,最终得出“母”问题的解;

看到分就感觉到这哪里是什么精髓,又看到治这个解释完全无言。去除了关键点,只能叫简,不能叫精髓。

查看算法导论解释。发现最精髓的红色部分,被词条完美的避过,真牛。

典型的分治:归并排序,分为小问题排序,再吧小排序合并为更大的排序,直到排完。

分:将问题划分为子问题,子问题的形式与元问题一样,只是规模更小

治:递归求解出子问题,如果子问题的规模足够小,则停止递归,直接求解。

合:将问题的解组合成原问题的解。

所以分治就是,必须分解大问题。如果分解后是另外一个问题。那没有任何用处,必须是形式一直,规模更小。如果规模可以无限小下去。也没有意义。必须小到一个时候,是一个很简单的问题,是可以解决的。那么就可以倒推到最先的大问题是可解决的。

分治常见算法

各种常见排序,一般都是分治思想。

递归思路,  天生分治思想。

原文地址:https://www.cnblogs.com/lsfv/p/10283813.html