分治算法一：基本概念（分而治之）分治就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题......直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。比如：二分查找，归并排序，快速排序，树的遍历等等任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于 n 个元素的排序问题，当 n=l 时，不需任何计算。*2 时，只要作一次比较即可排好序。n=3 时只要作 3 次比较即可，…。而当 n 较人时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。二：基本思想分治设计思想：将一个大的问题，分解成一个个小的，相同类型的问题，然后逐个击破各个小问题，最后将小问题逐步合并，得到最终的解。（可能会用到递归，人问题里包含小问题，找到规律然后解决）分治基本策略：对于一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n较小）则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。三：分治使用情况1）该问题的规模缩小到一定的程度就可以容易地解决2）该问题可以分解为相同类型的小问题（前提）3）利用该问题分解出的子问题的解可以合并为该问题的解；（关键）4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。四：基本步骤（1）划分：把问题的实例划分成子问题（2）求解：若是子问题比较简单，就直接解决，否则递归求解子问题（3）合并：合并子问题的解得到原问题的解课前引导：一：分段函数例如：高中数学中的分段函数也是类似分治思想的体现，如看图求 y 关于x 的表达式。一个分段函数，反映的是 x 与 y 的关系，简单來说，就是在 R 的范围内将 y 的表达式表示出來，那么这时候利用分治的思想，将 R 区间划分为小区间，然后分别求出各个小区间的表达式，最后合并起來，完成 y 关于 x 的表达式的求解二：大整数乘法123345678*3=370037034在这里我们可以这样写：123*3=369345*3=1035678*3=2034组合在一起是 36910352034o对比发现，当使用千进制...
