常用算法设计方法5

发布时间：2006-07-25 12:02 点击：

分页:上一页 1 2 3 4 5 6 7 [8] 9 10 下一页 后10页

    任何一个可以用计算机求解的问题所需的计算时间都与其规模

N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于

n个元素的排序问题，当

n=1时，不需任何计算；

n=2时，只要作一次比较即可排好序；

n=3时只要作

3次比较即可，…。而当

n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

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

    如果原问题可分割成

k个子问题（

1<k≤

n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

2、分治法的适用条件

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

分页:上一页 1 2 3 4 5 6 7 [8] 9 10 下一页 后10页

版权申明:未经书面授权请勿转载本站信息!!作品版权归所属媒体与作者所有!!

发表评论：

匿名发表

用户名:

查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任
留言板管理人员有权保留或删除其管辖留言中的任意内容
本站提醒：不要进行人身攻击。谢谢配合。