用主定理求解以下两个递归方程,关键步骤写上即可: 1. T(n)=9T(n/3)+5n2 2. T(n)=4T(n/5)+7n
时间: 2024-06-02 09:13:22 浏览: 137
递归方程求解
1. 针对第一个递归方程,我们首先需要确定主定理的三个参数:a=9, b=3, f(n)=5n^2。然后,我们可以计算出log_b^a = log_3^9 = 2,因为3^2=9。接下来,我们可以应用主定理公式:T(n) = Θ(n^log_b^a log n) = Θ(n^2 log n)。因此,第一个递归方程的时间复杂度为Θ(n^2 log n)。
2. 针对第二个递归方程,我们同样需要确定主定理的三个参数:a=4, b=5, f(n)=7n。然后,我们可以计算出log_b^a = log_5^4 < 1,因为5^1=5>4。接下来,我们可以应用主定理公式:T(n) = Θ(n^log_b^a) = Θ(n^log_5^4) ≈ Θ(n^0.86)。因此,第二个递归方程的时间复杂度为Θ(n^0.86)。
阅读全文