计算机算法基础第三版.doc

在下列情况下求解递归关系式4.2g(n) T(n)=2T(n/2)f(n)n足够小 否则 当n=2kg(n)=O (1)和f(n)=O(n) n=2kg(n)=O (1)和f(n)=O (1) 解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k) =22T(2k-2)+21f(2k-1)+ f(2k) =? =2kT (1)+2k-1f