文档介绍：第2章递归与分治策略
学习要点:
理解递归的概念。
掌握设计有效算法的分治策略。
通过下面的范例学习分治策略设计技巧。
(1)二分搜索技术;
(2)大整数乘法;
(3)Strassen矩阵乘法;
(4)棋盘覆盖;
(5)合并排序和快速排序;
(6)线性时间选择;
(7)最接近点对问题;
(8)循环赛日程表。
学习如何求解递归式这对于分析递归算法非常有用,主要有5种方法求解递归式。
(可以不需要知道常数系数确切是多少,仅需要猜它的形式,如n2 ,再试图解出它的常数。即先推测递归方程的显式解)
。验证是否这个递归式,按照数学归纳法满足条件。即用数学归纳法证明推测的正确性。
。
例1:T(n)=4T(n/2)+n; T(1)=1;
(n)=O ( n3 );想办法证明T(n)≤c * n 3
(k ) ≤c k3 ( k=n/2)即对k满足T(n)=O ( n3 ),即有T(n/2 ) ≤c (n/2)3
T(n)=4T(n/2)+n (对T(n/2)即对k+1看是否满足假设)
≤4c (n/2) 3 +n
= c/2* n 3 +n
= c * n 3 –(c/2* n 3 – n )
≤ c * n 3 (c/2* n 3 – n ≥0,即只要c ≥2就可以)
因此递归式的上界是O ( n3 );
例1:T(n)=4T(n/2)+n; T(1)= θ(1 );
(n)=O ( n2 );根据符号O的定义,对n>n0,有T(n) ≤ c n2
(k ) ≤c k2 ( k<n )
把这个解代入递归方程,得到
T(n)=4T(n/2)+n
≤4c (n/2) 2 +n
= c* n 2 +n
= c * n 2 –(–n)
而–n不是一个正数,无法得出c * n 2 –(–n) ≤ c * n 2
但假定归纳假设条件为:
T(k ) ≤c1k2 -c2 k ( k<n ) 这里减去c2 k ,因其是低阶项,不会影响到n足够大时的渐近性),
因此T(n)=4T(n/2)+n
≤ 4(c1 (n/2) 2 -c2 (n/2) )+n
= c1n2 +n - 2c2 n
= c1n2 - c2 n -(c2 n - n)
≤ c1n2 - c2 n (要满足条件 c2 n – n ≥0, 即只要 c2 –1 ≥0,即c2 ≥ 1即可)
即T(k ) ≤c1k2 -c2 k ,对任意的c1, c2 ≥ 1成立;
但必须注意c1要足够大,因为:
基本情况T(1) ≤c1 - c2
而T(1)= θ(1 )即T(1)是常数,我们需要选择c1 ,至少比c2大,而c2 ≥ 1,因此c1要足够大。
如何求出下界,解决办法之一是假设T(k ) ≥ c1k2 -c2 k ( k<n ),其余步骤类似。
因此递归式的上界是O ( n2 );
练习1:T(n)=4T(n/2)+n; T(1)= θ(1 );
(n)=O ( nlogn );
代换法求解递归式需要先猜出答案大概是多少,这比较困难。