递归方程组渐进界的求法

递归方程组的渐进界求解通常可以使用主方法（Master Theorem）或者递归树法（Recursion Tree Method）。

主方法适用于形如 $T(n) = aT(\frac{n}{b}) + f(n)$ 的递归式，其中 $a$ 和 $b$ 是常数，$f(n)$ 是非递归部分的复杂度。根据 $f(n)$ 的渐进增长速度和 $a$、$b$ 的大小关系，可以得出递归式的渐进界。具体来说，若 $f(n) = O(n^{\log_b a - \epsilon})$，则 $T(n) = \Theta(n^{\log_b a})$；若 $f(n) = \Theta(n^{\log_b a})$，则 $T(n) = \Theta(n^{\log_b a} \log n)$；若 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且对于某个常数 $c < 1$，存在正整数 $n_0$ 使得对于所有 $n \geq n_0$，有 $af(\frac{n}{b}) \leq cf(n)$，则 $T(n) = \Theta(f(n))$。

递归树法则是通过画出递归树，计算每一层的贡献，最后求和得到总的复杂度。这种方法比较直观，但是当递归深度较大时，计算比较繁琐。