分治法

2020-03-19 本文已影响0人 tangrl

前言

这学期学算法设计与分析，因为在家看直播学效率不如在学校高，故在此记录学习过程中遇到的问题和学到的东西，希望能帮助到别人也能帮助自己更加牢固的掌握知识。

分治法是什么

分治法，顾名思义就是分而治之，即将一个大问题分解为若干个不相交的同类型的小问题,分别解决每个小问题(因为是同类型的问题,所以可以递归地求解;当问题规模足够小时,就直接求解),然后将得到的结果重新组合成为大问题的解。

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

使用分治法解决问题的步骤

(1) 分: 将原问题分解为同类型不相交的若干子问题
(2) 治: 递归地解决这些子问题;当规模足够小时,可以直接求解
(3) 合: 将子问题的解合并为原问题的解

分治法适用情况

如果原问题可以分割成k个子问题，1<k<=n，且这些子问题均可解并且利用这些子问题的解求出原问题的解，那么分治方法就是可行的。
例如，二分查找就是可以用分治法的典型问题。第一步分: 如果中位元素不是要找的,将n个元素的序列分成两个含有n/2个元素的子序列。第二步治: 递归查找其中⼀一个子序列直到序列只有一个元素。第三步合: 返回查找结果。