用主定理求解以下两个递归方程，关键步骤写上即可： 1. T（n）=9T（n/3）+5n2 2. T（n）=4T（n/5）+7n

1. 根据主定理，T(n) = aT(n/b) + f(n) 的形式，其中 a = 9，b = 3，f(n) = 5n^2。
首先计算 logb(a) = log3(9) = 2，因为 f(n) = Θ(n^2) = Ω(n^logb(a)+ε)，其中 ε = 0.5，所以根据主定理，T(n) = Θ(n^logb(a)) = Θ(n^2)。

2. 根据主定理，T(n) = aT(n/b) + f(n) 的形式，其中 a = 4，b = 5，f(n) = 7n。
首先计算 logb(a) = log5(4) < 1，因为 f(n) = Θ(n) = O(n^logb(a)-ε)，其中 ε = 0.5，所以根据主定理，T(n) = Θ(n^logb(a)) = Θ(n^0.861)。

相关问题

用主定理求解以下两个递归方程， 1. T（n）=9T（n/3）+5n2 2. T（n）=4T（n/5）+7n

1. 根据主定理，对于递归形式 T(n) = aT(n/b) + f(n)，其中a≥1，b>1，f(n)是一个渐进正函数，可得到以下结果：
- 如果 f(n) = O(n^logb a - ε)，其中 ε > 0，则T(n) = Θ(n^logb a)。
- 如果 f(n) = Θ(n^logb a logk n)，其中 k ≥ 0，则 T(n) = Θ(n^logb a logk+1 n)。
- 如果 f(n) = Ω(n^logb a + ε)，其中 ε > 0，且af(n/b) ≤ cf(n)，其中 c < 1，那么 T(n) = Θ(f(n))。

对于 T(n) = 9T(n/3) + 5n^2，可以看成a=9，b=3，f(n)=5n^2，因此：
- logb a = log3 9 = 2
- f(n) = O(n^logb a - ε)，其中 ε > 0，因为 n^2 = O(n^2+ε)，所以 f(n) = O(n^2)
- 因此，T(n) = Θ(n^log3 9) = Θ(n^2)

对于 T(n) = 4T(n/5) + 7n，可以看成a=4，b=5，f(n)=7n，因此：
- logb a = log5 4 < 1
- f(n) = Ω(n^logb a + ε)，其中 ε > 0，因为 n^1+ε = Ω(n)，所以 f(n) = Ω(n)
- 由于 af(n/b) = 4f(n/5) = 4(7n/5) = 28n/5，而不满足 af(n/b) ≤ cf(n)，其中 c < 1，因此无法套用主定理。
- 但是可以使用递归树法来解决，每个节点有4个子节点，每个子节点处理大小为 n/5 的问题，因此每层的贡献为 4*(7n/5)，即 28n/5，递归树的高度为 log5 n，因此总复杂度为 Θ(n^log5 4) = Θ(n^0.861)，约为O(n)的复杂度。

回答完毕。

采用主方法求解以下递归方程：T(n)=1 当n=1时 T(n)=4T(n/2)+n^2 当n>1时

根据主方法，递归方程可以表示为：T(n) = aT(n/b) + f(n)，其中a = 4, b = 2，f(n) = n^2。

根据主定理的第一种情况，如果f(n) = O(n^c)且logb(a) < c，则T(n) = Θ(n^c)。

对于这个递归方程，c = 2，因为f(n) = n^2。logb(a) = log2(4) = 2，也小于c。因此，我们可以得出：T(n) = Θ(n^2)。

因此，递归方程的解为T(n) = Θ(n^2)。