function - 两个递归函数之和的复杂度？

Question

我需要计算以下递归函数的复杂度： T(n)=T(n/4)+3M(n/4)+11n-18 where M(n)=7M(n/4)+36n-52对于如下初始条件：T(1)=1 和 M(1)=6

如何计算 T(n) 的复杂度？我知道如何用一个递归函数来做，但是这次一个公式中包含两个递归函数，我不知道如何处理这个问题？

基于主定理有一个通用公式： 令 M(n)=aM(n/b)+cn+d+fn^k 且 M(1)=e 则 M(n) 的复杂度计算如下：

--如果a不等于b且f=0，那么M(n)的解为：M(n)=(e+(bc/(ab)) + d/a-1)n^log_ba - ( bc/ab).n+d/a-1

我想用这个通用公式来计算上面 T(n) 的复杂度。有人可以帮我解决这个问题吗？

标签： functionrecursioncomplexity-theorymaster-theorem

Answer 1

注意 T 引用了 M，但 M 只引用了它自己。这意味着您可以在此处执行两步过程：

1. 求解 M(n)。
2. 将解代入 T(n)，仅根据自身给出 T(n) 的递归，然后求解 T(n)。

从您的问题来看，您似乎正在寻找一个精确的解决方案，但如果您只是渐近地关心，您可以使用主定理来获得如下解决方案：

1. M(n) = Θ(n ^{log ₄ 7} )
2. T(n) = T(n / 4) + 3M(n / 4) + O(n) = T(n / 4) + Θ(n ^{log ₄ 7} )，求解为 Θ(n ^{log ₄ 7} )。