Algorithm 版 (精华区)

发信人: Lerry (第一次有失恋的感觉), 信区: Algorithm
标  题: 分治法的基本思想
发信站: 哈工大紫丁香 (2002年03月12日11:03:20 星期二), 站内信件

分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，
越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1
时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…
。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是
相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题
，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题
的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问
题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，
可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接
求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在
算法设计之中，并由此产生许多高效算法。


--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]