第二章 2.化简递推关系式 ∴g(n)=0(1) ∴可令g(n)=c1(或简单令g(n)=1) 同理 f(n)=0(n) ∴可令f(n)=c2n(或简单令f(n)=n,或f(n)=c2n+b), 可设c1=C2=C 化简 T(n)=2T(n/2)+f(n) 2T(n/2)+cn =4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn 2kT(n/2k)+kcn 若n=2,则k=logn .T(n)=cn+cnlogn=o(nlogn) 当n∈[2k,2k+1),T(n)=cn+ cologne=e( nlogn)第二章 2. 化简递推关系式 ∵g(n)=O(1) ∴可令 g(n)=c1(或简单令g(n)=1) 同理， ∵f(n)=O(n) ∴可令 f(n)=c2n(或简单令f(n)=n，或f(n)=c2n＋b), 可设c1=c2=c 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+cn =4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn =… =2kT(n/2k)+kcn 若n=2k ,则k=logn ∴T(n)=cn+cnlogn=O(nlogn) 当n∈[2k,2k+1), T(n)=cn+cnlogn=Θ(nlogn)