分治法介绍
分治法:
1、介绍:
分治法(Divide and Conquer),即分而治之,是一种非常重要的算法设计思想。我们能够使用分治思想解决的问题通常结构上是 递归的:算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。反过来,不是所有 递归问题都可以用分治法来解决,包括以后可能提到的动态规划。
2、步骤:
分治模式在每层递归时都有三个步骤:
- 分:将原问题分解为多个小问题;
- 治:递归求解子问题,以及子问题的子问题,往往子问题规模最小时都是可以直接得出结果;
- 合并:将子问题的解组成原问题的解;
3、分析:
分治法的优点之一在于它的运行时间非常容易确定,例如归并排序的运行时间就可以写成如下的表达式:
- 这种表达式被称作递归式,使用递归式可以很自然的划分分治算法的运行时间;
- 表示这一算法的最坏情况运行时间;
递归式的求解主要有三种方法:
1)、代入法:
猜测一个界,然后用数学归纳法证明;
2)、递归树法:
将递归式转换成一棵树,其结点表示不同层次的递归调用产生的代价;
可以得出代价为,也就是;
- 计算机科学中一般将2为底的对数写作
lg
; - 分析过程不一定完美,只是提出思考的方式,深入学习可以看《算法导论》。
3)、主方法:
利用公式求解特定形状的递归式:;
主方法,也被称为主定理的公式不在这里多讲,具体证明也可以去看前面提到的《算法导论》;
- 在我看来,递归树法最直观,而主方法更精确一些;
4、应用:
分治思想的运用非常广泛,甚至超过计算机科学的范畴;二分查找以及归并排序就是典型的应用;