已知递归关系式怎么求渐近时间复杂度

要求解递归函数的渐近时间复杂度，可以使用主定理（Master Theorem）。主定理是一种用于求解分治算法渐进时间复杂度的公式。

主定理的公式如下：

T(n) = aT(n/b) + f(n)

其中，a是递归调用的子问题个数，b是每个子问题的大小，f(n)是除了递归调用之外的其它操作的代价，如循环等。

根据主定理，可以将递归函数的渐进时间复杂度分为三种情况：

1. 如果f(n) = O(n^k)，其中k>=0，且a<=b^k，则T(n) = O(n^k log n)。

2. 如果f(n) = O(n^k)，其中k>=0，且a=b^k，则T(n) = O(n^k log n)。

3. 如果f(n) = O(n^k)，其中k>=0，且a>=b^k，则T(n) = O(n^log_b a)。

需要注意的是，主定理只适用于满足上述形式的递归函数。对于不满足这种形式的递归函数，需要使用其他方法求解渐进时间复杂度。