核心：掌握主方法求解递归关系式
分治算法
本质其实就是将一个问题分解为若干个规模较小的相同子问题,分而治之。
解题步骤
-分解问题
将要解决的问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。
-问题治理
求解各个子问题,由于各个子问题和原问题的形式相同,只是规模较小,因此当子问题划分的足够小时,我们就可以用较为简单的方法去解决。
-问题合并
按照原问题的要求,将子问题的解逐层的合并构成原问题的解.一句话总结,分治法就是将一个难以直接解决的大问题,分割成规模较小的相同子问题,以便各个击破,分而治之。
案例分析
二分猜数
我们一定都玩过猜数游戏,现在我们两个人玩这个游戏,我在我的手心写一个100以内的整数,并且只能给你大了或小了的提示,并且只有三次机会,那如何才能以最快的速度猜出来呢?
解题思路:
从问题的描述来看,如果是n个数,最坏的情况我们得猜n次才可以成功,其实我们没有必要非得一个个的去猜,这显然是一个笨方法,因为这些数是有序的,我们可以按照折半查找的方式,每次和中间的元素去比较,如果每次比中间的部分大,去后半部分找,比中间部分小,去后半部分找.那我们现在思路有了,可以将问题抽象描述出来:给定n个元素,假设这些元素是有序的,从中查找特定元素x.
解题思想:
将有序序列先大致分为数目相等的两组,然后去中间的元素与特定的查找元素进行比较,如果x等于中间元素,查找成功,如果x小于中间元素,在前半部分继续执行分解和治理操作,如果x大于中间元素,去后半部分进行分解和治理.算法设计:使用一维数组S[]放置该有序序列,设置变量low和high表示查找的上下界,middle表示中间的位置,x为特定的查找元素.
