分治法算法总结

目录

1. 分治算法
   1.1常见算法用例
   1.2个人理解

2. 分治算法时间复杂度的计算。
   2.1代入法 （尽量别用）
   2.2递归树（次推荐）
   2.3主定理（推荐）

---

正文

分治算法定义：对于一个问题，能够将该问题转化更小规模的同种问题形式,所有的例子所有的必然含有三个步骤：分解，解决，合并。

1.1常见算法

1.归并排序：对于输入规模为n的数组进行排序。

解法：可以转化为两个长度为n/2的问题求解，如此分解。当分解的数组中只有一个元素时，此时元素必然有序，关键的难点解决在于合并两个有序数组（当然这只是相对来说）。

2.最大子数组问题：对于一个存在正数和负数的数组，求解出它的一个子数组，子数组满足如下条件：在所有的子数组集和中，该子数组和必须为最大。

解法：分解：将原来的子数组分解为更小的数组。解决：当对于数组规模为1的情况下，数组最大子数组即为本身。合并:对于以求出最大子数组的两个子数组，求取这两个数组拼接在一起时的最大子数组。合并后的子数组有且仅有三种情况：左边的的最大子数组，右边的最大子数组，以及这样的子数组：从左穿过右的最大子数组。现在问题转变为如何求取贯穿中间的子数组，此问题又转变为：给定一个数组的起点，如何求取从此数组起点开始的总和最大的子数组（该问题简单。）。那么如何求取贯穿中间的子数组可以用上面的解法可以解决，至此解决完毕。

3.矩阵求和问题

对于此问题，列举了两种算法：按照定义计算，时间复杂度为n3,简单的分治算法：矩阵分块。但算法复杂度还是n3，还需要小心元素控制下标进行分块，还容易弄错。strassen算法引入了7个辅助矩阵，算法本身没什么好说的，说也说不清楚，需要幸运以及努力才能发现这种算法。这个在矩阵论中提及过，复杂度为nlg7。

1.2个人理解

个人理解分支法最难的一步，是合并这一步如何吧，我当将问题把它分解，然后找准他的基本情况之后，这样其实已经解决了分解和解决两步了。然后如何合并问题，因为合并：从原来的那个问题转化为大问题我觉得是比较难的。就比如在最大子数组问题中。我就曾经被这个合并这个问题所困扰过，在这个问题中所反映出来的就是说，你要把问题要更加的分解，更加的去细致的去考虑，把问题给明确，然后去思考。

2.时间复杂度的计算

2.1代入法

2.1.1猜测解的形式，这个你要根据以往的经验来判断，比如说你之前见过一些类似的方程，然后你猜测这个方程的解也可能是这个解。

2.1.2数学归纳法求出解中的常数，并证明及时正确的。这个就是说：把猜测的解代入函数，然后我能够代入之后所出来的显示能够符合原来的猜测的形式。具体例子见算法导论P48。

2.2.2递归树

我们可以按照分治法的算法，可以将它的过程分解按照树的形式来展示，然后每个节点可以以标记他这个节点所花费的代价，然后展开之后，然后计算各层的代价。然后将各层的代价相加得到算法复杂度。

注意：在计算各层代价相加的时候，我们通常为了简便计算，我们会以树高乘以各层的代价。但注意此种情况仅仅在展开为完全二叉树并且每层代价都相同的情况下。

2.2.3主方法

对于递归式：T(n)=a*T(n/b)+f(n)。有如下三种结论：

注意：
1.需要注意条件中的多项式渐进，以及第条3结论条件中的正则条件。
2.主方法并未覆盖所有情况,有些未覆盖的情况只能用代入法和递归树法解。

完。