5 / 8Р对各层求和，第一层的和是n2 ,第二层的 和是5/16n2 ((n/4)2 +(n/2)2 ),第三层的和是 52 /162 n2 ((n/16) 2 + (n/8) 2 +(n/8) 2 + (n/4) 2))….可以看出这是一个等比数列，对各层 累加， 即n2 + 5/16n2 +52 /162 n2 +… + 5k/16kn2 +… (1) (1) ≤(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2 Р Р等比数列性质： 1+1/2+1/4+1/8+…=2; 因为对二进制而言1+1/2=1.1 1+1/2+1/4=1.11 1+1/2+1/4+1/8+…=1.111…=2; 而(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2中 5/16 所以(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2 ≤2 n2Р Р故递归式T(n)= T(n/4)+ T(n/2)+n2的上界是 O (n2),下界是Ω (n2) (T(n)= T(n/4)+ T(n/2)+n2 ≥ n2)Р递归树法又名递推法T(1)=1 T(n)=2T(n/2)+n2(n≥2) T(n)=2T(n/2)+ n 2 =2(2T(n/2 2)+(n/2) 2 )+ n2 =22T(n/22) +n2/2+ n2 =22(2T(n/23)+(n/22)2)+n2/2+ n2 =23(2T(n/23)+ n2/22+ n2/2+ n2 … =2kT(n/2k)+∑n2/2i (i从0到k-1) РР РРРР2016全新精品资料-全新公文范文-全程指导写作 –独家原创 6 / 8
全文预览
