算法设计与分析2

1、算法分析理论 -递归程序的复杂性分析宫秀军天津大学计算机科学与技术学院http:/ 递归递归: Recurrences RelationnRecurrences RelationqA recurrence relation is an equation which is defined in terms of itself. nSolving RecurrencesqRecursion treeqIteration methodqSubstitution methodqMaster methodMerge-SortMerging two sorted arraysMerge-Sort Anal

2、ysis假定n=2h ,h0,上式变为2T(n/2)Recurrence for merge sortn隐含假定n=2h.n以cn代替(n),不影响渐近分析的结果.n“If n=1”,更一般的情形是“if nn0, T(n)=(1)”：q可找到足够大常数c1,使得 T(n)c1 if n 0 为常数.n递归展开到T(n0),会导致推导的麻烦.所以展开到T(1).然后在从前n0个T(n)的值确定渐近分析的常数.Recursion treenSolve T(n) = 2T(n/2) + cn, where c 0 is constant.Recursion treenSolve T(n) = 2T

3、(n/2) + cn, where c 0 is constant.Recursion treeMerge Sort 小结n ( (n n lg lg n n) )比比(n n2 2) )增增长长的慢的慢.n所以所以,merge sort 渐近渐近(asymptotically)优于插优于插入排序入排序.n实际上实际上, merge sort 优于优于 insertion sort 仅当仅当 n 30 or so.n1000*nlogn算法当算法当n比较小时未必比比较小时未必比n2算法要算法要快快. n足够大时前者才能看出优势足够大时前者才能看出优势.迭代法 1nT(n)=2T(n/2)+cn

4、 =2(2T(n/22)+cn/2)+cn =22T(n/22)+cn+cn =2hT(n/2h)+hcn当 2h=n, then =nT(1)+logn*cn =(nlogn)当当n2hn2hn n= ( (2h), h= ( (logn)nT(2h) T(n) T(2h+1).n所以所以,(h2h)T(n)(h+1)2h+1)n(h+1)2h+1)=(h2h+1+2h+1) =(h2h+1)=(h2h) n所以所以T(n)=(h2h)=(nlogn)迭代法 2nT(n)=4T(n/2)+n =4(4T(n/22)+n/2)+n =42T(n/22)+n+2n =43T(n/23)+n+2n

5、+22n =4hT(n/2h)+n(1+2+2h-1) =n2T(1)+n(2h-1) =(n2) 较一般的递归式较一般的递归式n较一般的递归较一般的递归:T(n)=aT(n/b)+cn, a,b是大于1的整数的整数,递归树方法仍可使用递归树方法仍可使用.n首先考虑首先考虑n=bh情形情形: T(n)=ahT(1)+cn(1+(a/b)+(a/b)h-1) = ahT(1)+cah(1+(a/b)+(a/b)h-1) n当当bhn h= ( (logn)n递归树等价于迭代展开递归树等价于迭代展开n很多递归式用递归树解不出来很多递归式用递归树解不出来,但递归树能提供直觉但递归树能提供直觉,帮助我

6、们用归纳法求解帮助我们用归纳法求解(Guess 归纳假设归纳假设).Substitution methodsnThe most general method:1. Guess the form of the solution.2. Verify by induction.3. Solve for constants.Example1nT (n) = 4T (n/2) + n （n=2h）nAssume that T (1)=(1).nGuess O(n3) :归纳假定为T (n)cn3. c是待定常数.n应用假定有:T (k) ck3 for k n .n归纳证明: T (n) cn3 并确定

7、常数c.Example (continued)nT(n)=4T(n/2)+n 4c(n/2)3+n =(c/2)n3+n =cn3-(c/2)n3-n) cncn3 3 取取 c2 and n1,不等式不等式(c/2)n3n0成立成立Example (continued)n还要检验初始条件是否满足归纳假设还要检验初始条件是否满足归纳假设.n初始条件为初始条件为: T(n)= = ( (1),当当 nn0 ,n0为常数为常数.n因为有常数因为有常数n0-1个T的值的值:T(1),T(n0-1)n所以我们可取所以我们可取c足够大足够大,使得使得T(n)cn3, 对对nn0 成立成立.nThis b

8、ound is not tight!Example (continued)nWe shall prove that T(n)=O(n2).nAssume that T(k)ck2 for kn:nT(n)=4T(n/2)+n 4c(n/2)2+n =cn2+nn归纳不能往下进行！归纳不能往下进行！ ContinuednIDEA: Strengthen the inductive hypothesis.nSubtract a low-order term.nInductive hypothesis: T(k)c1k2 c2k for k1Continued nFor 1n 0 T(n) = (n

9、logb a).qf(n) = (nlogb a) T(n) = (nlogb a lg n).qf(n) = (nlogb a + ), for 0,and a f(n / b) c f(n),for c 0,为某一常数某一常数 f(n)的增长渐近地慢于的增长渐近地慢于nloga (慢慢 n 倍倍).nSolution: T(n)=(nloga) .The Master Method:情形情形2n情形情形2: f(n)= (nloga lgkn) k0 为某一常数为某一常数.nf(n) 和和 nloga 几乎有相同的渐近增长率几乎有相同的渐近增长率.因为因为nloga lgkn=O(n+lo

10、ga) , for any 0.nSolution: T(n)= (nloga lgk+1n) .The Master Method:情形情形3n情形情形3nf(n)=(nloga +) 0为一常数为一常数. f(n)多项式地快于多项式地快于nloga (by an n factor),nf(n) 满足以下规则性条件满足以下规则性条件: af(n/b)cf(n), 0cf(bh)c(ah/bh) )nT(n)=ahT(1)+akf(bh-k),(: k=0,h-1)nT(n)ahT(1)+ca ak k( (ah-k/b(h-k) =ahT(1)+cah(1 1/b(h-k) ahT(1)+c

11、ah1k1,0,无穷和收敛) n所以T(n)=O(nloga); 显然, T(n)=(nloga)Proof of Case2nf(n)= (nloga lgkn), n=bh, nloga=ahnf(n)cah(hlgb)k=cahhk(lgb)k nT(n)ahT(1)+cahi i k (lgb)k ahT(1)+cah hk+1 (lgb)k =ahT(1)+ cah hk+1 (lgb)k+1 /lgb=c(nlogalgk+1n)n上面推导中用到上面推导中用到: 1k+hk= (h(hk+1k+1) )裴波那契(Fibonacci)序列n序列F0=F1=1,Fi=Fi-1+Fi-2

12、 (i1)称为Fibonacci序列. 以下算法计算第n个Fibonacci数: proc F(n) if n1 return(1) else return( F(n-1)+F(n-2); end procn令t(n)为算法执行的加法次数,有: t(n)=0 for n=0,1 t(n)=t(n-1)+t(n-2)+1 特别t(2)=1,t(3)=2 续n因为t(n-1)t(n-2),有 t(n)2. 用归纳法易证: t(n)2n n又有t(n)2t(n-2)2k-1t(2)=2k-1 n=2k 2k-1t(3)=2k n=2k+1nt(n)=nt(n)=n算法有指数的时间复杂度.n实际上这是因递归引起的大量的重复计算而非问题本身的难度所致.可设计一非常简单的线性时间复杂度的迭代算法. )2(n)2(nAPT Topics on Algorithm PerformancenDo performance analysis on algorithms from your per