【算法】分治法所能解决的问题的特征总结

【算法】分治法所能解决的问题的特征总结

分治法的设计思想：

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。**

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排。n=2时，只要作一次比较即可排好序。n=3时序问题，当n=1时，不需任何计算只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

分治法所能解决的问题一般具有以下几个特征：

1.可缩性。问题的规模缩小到一定的程度就可以容易地解决；

2.最有子结构性。问题可以分解为若干个规模较小的相同问题；

3.可合性。利用该问题分解出的子问题的解可以合并为该问题的解；

4.独立性。该问题所分解出的各个子问题是相互独立的，即子问 题之间不包含公共的子子问题。## 标题

分治思想与递归就像一对孪生兄弟，经常同时应用在算法设计中，并由此产生高效的算法！

设计递归的思路

最小子结构
子结构
最小子结构与子结构之间的关系
寻找这三个问题的答案时，可以先手算前几个情况的答案，然后找规律。
如果能回答上来这三个问题，题目便迎刃而解了

什么时候考虑递归

具有以下特征的问题可考虑递归求解：

当问题和子问题具有递推关系，比如杨辉三角、计算阶乘（后文讨论）。
具有递归性质的数据结构，比如链表、树、图。
反向性问题，比如取反。
总结下来，最根本的还是要抓住问题本身是否可以通过层层拆解到最小粒度来得解。
若有兴趣，请点击->递归的详细解释

头递归与尾递归

通过下面的例子来体会头递归与尾递归的区别

//#incldue<链表定义>                 偷懒：）
void print1(LinkList L){if(L==NULL) return;print1(L->next);  //先递归到链表最尾部 再逆序输出printf("%d ",L->data);//输出结果 10 9 8 7 6 5 4 3 2 1
}
void print1(LinkList L){if(L==NULL) return;printf("%d &