求解递归方程的方法:递归树法 示例一 T(n)=2T(n/2)+n-1,求T(n)上界 将每一层的代价求和:(假设k层,k=nlogn) T(n)=kn + n-1 + n-2 + …… + n-2^(k-1) T(n)=kn - (2^k -1)=nlogn - n + 1=O(nlogn) 示例二 根据式 T(n)=3T(n/4)+ θ(n2 ),写出其递归树,并计算其时间复杂度。(要求写出时间复杂度的推导过程 ) 深度求解 将每一层代价求和