Question

4有递归方程 T(n)=3T(n/2)+(n),T(1)=(1) ) ,解此方程可得 T(n)=

Answer 1

问：4有递归方程 T(n)=3T(n/2)+(n),T(1)=(1) ) ,解此方程可得 T(n)=

答：T(n) = O(nlog₂n)该递归方程可使用主定理（Master Theorem）求解。根据主定理，对于形如 T(n) = aT(n/b) + f(n) 的递归式，其中 a ≥ 1，b > 1，f(n) 是一个渐进正函数，有以下三种情况：如果 f(n) = O(n^(log_b(a)-ε))，其中 ε > 0，则 T(n) = Θ(n^(log_b(a)))如果 f(n) = Θ(n^(log_b(a)))，则 T(n) = Θ(n^(log_b(a)) * log n)如果 f(n) = Ω(n^(log_b(a)+ε))，其中 ε > 0，并且存在常数 c 1 和 n₀ > 0，使得对于所有的 n ≥ n₀，有 af(n/b) ≤ cf(n)，则 T(n) = Θ(f(n))根据上述公式，我们可以得到 a=3, b=2, f(n)=n。因此，log_b(a) = log₂3f(n) = n = Θ(n^1)log_b(a) > 1根据情况 2，我们可以得到 T(n) = Θ(n^(log_b(a)) * log n) = Θ(n^(log₂3) * log n) = O(nlog₂n)。