4.2在下列情况下求解递归关系式T(n)二Ig(n)n足够小n=2T(n/2)+f(n)否则当n=2kg(n)=0(1)和f(n)二0(n)；n=2kg(n)=0(1)和f(n)二0(1)。解：T(n)=T(2k)=2T(2k-i)+f(2k)=2(2T(2k-2)+f(2k-i)+f(2k)=22T(2k-2)+21f(2k-1)+f(2k)=2kT(1)+2k-1f(2)+2k-2f(22)+2of(2k)=2kg(n)+2k-1f(2)+2k-2f(22)+2of(2k) 当g(n)=0(1)和f(n)二O(n)时，不妨设g(n)=a，f(n)=bn，a，b为正常数。贝VT(n)=T(2k)=2ka+2k-1*2b+2k-2*22b+2o*2kb=2ka+kb2k=an+bnlogn=0(nlogn) 当g(n)=O(1)和f(n)二0(1)时，不妨设g(n)=c,f(n)=d,c,d为正常数。则T(n)=T(2k)=c2k+2k-1d+2k-2d+2od=c2k+d(2k-1)=(c+d)n-d
