算法分析(2)_2016

1、算法分析（2）Pseudocode (伪代码伪代码)Solving Recurrences(解递归解递归)o While-循环最坏情形(j).o While-循环平均情形(j/2),当插入位置有相同概率时.伪代码伪代码-插入排序插入排序o “”表示”赋值“(assignment).o 忽略数据类型、变量的说明等与算法无关的部分.o 允许使用自然语言表示一些相关步骤o 伪代码突出了程序使用的算法. 插入排序实例插入排序实例插入排序分析o 最坏情形：输入数据已按倒序排列o 平均情形：输入数据为所有可能的排列o 插入排序是否是最快的排序算法？o 当n很小时，结论肯定o 当n很大时，不一定)()()(

2、22njnTnj)()2/()(22njnTnj最优二叉树(optimized binary tree)for m 2 to n (1) do for i 0 to n-m (1) do j i + m (1) w(i, j) w(i, j-1) + P(i) + Q(j) (1) c(i, j)minilj c(i, l-1) + c (l, j) + w(i, j) W(n,n),P(n),Q(n),c(n,n) 是算法使用的数组,假定已初始化.最优二叉树：时间复杂度分析o minilj c(i, l-1) + c (l, j) : (j-i)=(m) o 内层循环:(m(n-m)；o 总

3、的时间复杂度： (2mnm(n-m)=(n3)解递归方程的方法解递归方程的方法p 递归树（Recursion tree）p 替代法（Substitution method）p Master方法（Master method）归并排序归并排序合并已排序的子序列合并已排序的子序列归并排序时间复杂度分析归并排序时间复杂度分析o Should be o 假定n=2h ,h0,上式变为2T(n/2)归并排序时间复杂度：递归方程归并排序时间复杂度：递归方程o 隐含假定n=2h.o 以cn代替(n),不影响渐近分析的结果.o “If n=1”,更一般的是“if nn0, T(n)=(1)”：指:可找到足够大常

4、数c1,使得 T(n)c1 if n 0 为常数.o 递归展开到T(n0),然后再从前n0个T(n)的值确定渐近分析的常数.o 展开到T(n0),有时会导致推导的麻烦，所以展开到T(1).递归树递归树递归树递归树o 解T(n) = 2T(n/2) + cn, 其中 c 0 是常数.递归树递归树o 解 T(n) = 2T(n/2) + cn, 其中 c 0 是常数递归树递归树递归树等价于迭代展开递归树等价于迭代展开o T(n)=4T(n/2)+n =4(4T(n/22)+n/2)+n =42T(n/22)+n+2n =43T(n/23)+n+2n+22n =4hT(n/2h)+n(1+2+2h-

5、1) =n2T(1)+n(2h-1) =(n2) o 很多递归式用递归树解不出来很多递归式用递归树解不出来,但递归树能提供直但递归树能提供直觉觉,帮助我们用归纳法求解帮助我们用归纳法求解(Guess 归纳假设归纳假设).结论结论o (n lg n)比比(n2)增长的慢增长的慢.o merge sort 渐近渐近(asymptotically)优于插入排序优于插入排序.o 实际上实际上, merge sort 优于优于 insertion sort 仅当仅当 n 30 or so.o 1000*nlogn算法当算法当n比较小时未必比比较小时未必比n2算法要算法要快快. n足够大时前者才能看出优势

6、足够大时前者才能看出优势.当当n2ho 2hn n= ( (2h), h= ( (logn)o T(2h) T(n) T(2h+1).o 所以所以,(h2h)T(n)(h+1)2h+1)o (h+1)2h+1)=(h2h+1+2h+1) =(h2h+1)=(h2h) o 所以所以T(n)=(h2h)=(nlogn)较一般的递归式较一般的递归式o 较一般的递归较一般的递归:T(n)=aT(n/b)+cn, a,b是大于1的的整数整数,递归树方法仍可使用递归树方法仍可使用.o 首先考虑首先考虑n=bh情形情形: T(n)=ahT(1)+cn(1+(a/b)+(a/b)h-1) = ahT(1)+c

7、bh(1+(a/b)+(a/b)h-1) o 当当bhn h= ( (logn)替代法o 解递归方程最一般的方法:1. Guess the form of the solution.2. Verify by induction.3. Solve for constants.例1oT (n) = 4T (n/2) + n （n=2h）o Assume that T (1)=(1).o Guess O(n3) :归纳假定为T (n)cn3. c是待定常数.o 应用假定有:T (k) ck3 for k n .o 归纳证明: T (n) cn3 并确定常数c.例(续)o T(n)=4T(n/2)+n

8、 4c(n/2)3+n =(c/2)n3+n =cn3-(c/2)n3-n) cncn3 3 取取 c2 and n1,不等式不等式(c/2)n3n0成成立立, 例(续)o 还要检验初始条件是否满足归纳假设还要检验初始条件是否满足归纳假设.o 初始条件为初始条件为: T(n)= = ( (1),当当 nn0 ,n0为常数为常数.o 因为有常数因为有常数(n0-1)个T的值的值:T(1),T(n0-1)o 所以可取所以可取c足够大足够大,使得使得T(n)cn3, 对对nn0 成立成立.o 该上界不是紧上界（该上界不是紧上界（tight bound）!例(续)o We shall prove th

9、at T(n)=O(n2).o Assume that T(k)ck2 for kn:o T(n)=4T(n/2)+n 4c(n/2)2+n =cn2+no 归纳不能往下进行！归纳不能往下进行！ 替代法（续）o IDEA: Strengthen the inductive hypothesis.o Subtract a low-order term.o Inductive hypothesis: T(k)c1k2 c2k for k1续o For 1n1, 为整数为整数, f(n)0.o 按按f(n)相对于相对于nloga 的渐近性质的渐近性质, 分三种情形进分三种情形进行分析行分析.o 这里

10、这里loga 指以指以b为底的为底的a的对数的对数logba.The Master Method:情形情形1o 情形情形1. f(n)=O(nloga), 0,为某一常数某一常数 f(n)的增长渐近地慢于的增长渐近地慢于nloga (慢慢 n 倍倍).o Solution: T(n)=(nloga) .The Master Method:情形情形2o 情形情形2: f(n)= (nloga lgkn) k0 为某一常数为某一常数.o f(n) 和和 nloga 几乎有相同的渐近增长率几乎有相同的渐近增长率.o Solution: T(n)= (nloga lgk+1n) .The Master

11、 Method:情形情形3o 情形情形3o f(n)=(nloga +) 0为一常数为一常数. f(n)多项式地快于多项式地快于nloga (by an n factor),o f(n) 满足以下规则性条件满足以下规则性条件: af(n/b)cf(n), 0cf(bh)c(ah/bh) )o 取充分大的取充分大的c,使使f(bi)c(ai/bi) ) 对对所有所有i i成立成立. .o T(n)=ahT(1)+akf(bh-k),(: k=0,h-1)o T(n)ahT(1)+ca ak k( (ah-k/b(h-k) =ahT(1)+cah(1 1/b(h-k) ahT(1)+cah1k1,

12、0,无穷和收敛) o 所以T(n)=O(nloga); 显然, T(n)=(nloga)Proof of Case2o f(n)= (nloga lgkn), n=bh, nloga=aho =f(bh)cah(hlgb)k=cahhk(lgb)k o 类似类似,f(bi) caiik(lgb)k. (取充分大的取充分大的c)o T(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)o 上面推导中用到上面推导中用到: 1k+hk= (h(hk+1k+1) )

13、Case 3o 反复应用规则性条件有反复应用规则性条件有: akf(n/bk)ckf(n) o 所以所以: akf(n/bk) ckf(n)o T(n)=ahT(1)+akf(n/bk)ahT(1)+f(n)ckahT(1)+f(n)(1-c)-1o 因为, f(n)=(nloga +),量级高于ah , 所以T(n)=O(f(n).o 又,T(n)f(n).所以所以,T(n)=(f(n)补充例题例题1：展开递归树:T(n)=T(1)+T(n1)+cn,并做渐近分析例题2：展开T(n)=T(0.1n)+T(0.9n)+(n)的递归树并计算递归树的深度和T(n)的渐近值.裴波那契(Fibonac

14、ci)序列o序列F0=F1=1,Fi=Fi-1+Fi-2 (i1)称为Fibonacci序列. 以下算法计算第n个Fibonacci数: proc F(n) if n1 return(1) else return( F(n-1)+F(n-2); end proco令t(n)为算法执行的加法次数,有: t(n)=0 for n=0,1 t(n)=t(n-1)+t(n-2)+1 特别t(2)=1,t(3)=2 续o 因为t(n-1)t(n-2),有 t(n)2. 用归纳法易证: t(n)2n o 又有t(n)2t(n-2)2k-1t(2)=2k-1 n=2k 2k-1t(3)=2k n=2k+1o t(n)=o 算法有指数的时间复杂度.o 实际上这是因递归引起的大量的重复计算而非问题本身的