典型错误 令g(n)=a,f(mn)=bn+c(a,b,c为常数) 则T(n)=2T(n/2)+bn+c =4T(n/4)+2bn+2c+bn+c =2T(n/2)+bn(1+2+…+2k-1) +c(1+2+…+2k-1) 2T(n/2k)+(bn+c)(2k-1) 故得,T(n)=(n2)
典型错误 令g(n)=a,f(n)=bn+c(a,b,c为常数） 则T(n)=2T(n/2)+bn+c =4T(n/4)+2bn+2c+bn+c =… =2kT(n/2k)+bn(1+2+…+2k-1) +c(1+2+…+2k-1) =2kT(n/2k)+(bn+c)(2k-1) 故得，T(n)=Θ(n2)
5.三分法 low mid2 high mid1=low L (high-low)/3] mil=(high+lon)/3」 mid2=high- LChigh-low)/3 2=2(high+low)/3
5.三分法 low mid1 mid2 high mid1=low + mid2=high - (high −low)/ 3 (high −low)/ 3 2 2( )/ 3 1 ( )/ 3 mid high low mid high low = + = +