求解递归方程的方法：递归树法

示例一

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 )，写出其递归树，并计算其时间复杂度。(要求写出时间复杂度的推导过程 )

深度求解

将每一层代价求和