递归树 对应于T()=T(nl2)+T(nl2)+n的递归树 T(size) nonrecursive cost T(n) n T(n/2) n/2 T(n/2) n/2 Tnl4④ n/4 T(n/4) n/4 T(nl④ n/4 Tnl4④ n/4 所有节点的非递归开销的和就是算法的开销 树的“高度”和“胖度”决定了节点的多寡 在非递归开销不变的情况下，降低“高度”、缩小“胖度”递归树 对应于 T(n)=T(n/2)+T(n/2)+n 的递归树 T(size) nonrecursive cost T(n) n T(n/4) n/4 T(n/4) n/4 T(n/4) n/4 T(n/4) n/4 T(n/2) n/2 T(n/2) n/2 所有节点的非递归开销的和就是算法的开销 树的“高度”和“胖度”决定了节点的多寡 在非递归开销不变的情况下，降低“高度”、缩小“胖度