两个递归函数之和的复杂性？
Complexity of the sum of two recursive function?
我需要计算以下递归函数的复杂度：
T(n)=T(n/4)+3M(n/4)+11n-18 其中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/(a-b)) + d/a-1)n^log_ba - (bc/a-b).n+d/a-1
我想用这个通用公式来计算上面T(n)的复杂度。有人可以帮我解决这个问题吗？
注意T引用了M，但是M只引用了自己。这意味着您可以在此处进行 two-step 处理：
- 求解 M(n)。
- 将解代入 T(n)，给出 T(n) 本身的递归，然后求解 T(n)。
从你的问题来看，你似乎在寻找一个精确的解决方案，但如果你只是关心渐进，你可以使用主定理得到如下解决方案：
- M(n) = Θ(nlog4 7)
- T(n) = T(n / 4) + 3M(n / 4) + O(n) = T(n / 4) + Θ(nlog 4 7)，求解为 Θ(nlog4 7).
我需要计算以下递归函数的复杂度： T(n)=T(n/4)+3M(n/4)+11n-18 其中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/(a-b)) + d/a-1)n^log_ba - (bc/a-b).n+d/a-1
我想用这个通用公式来计算上面T(n)的复杂度。有人可以帮我解决这个问题吗？
注意T引用了M，但是M只引用了自己。这意味着您可以在此处进行 two-step 处理：
- 求解 M(n)。
- 将解代入 T(n)，给出 T(n) 本身的递归，然后求解 T(n)。
从你的问题来看，你似乎在寻找一个精确的解决方案，但如果你只是关心渐进，你可以使用主定理得到如下解决方案：
- M(n) = Θ(nlog4 7)
- T(n) = T(n / 4) + 3M(n / 4) + O(n) = T(n / 4) + Θ(nlog 4 7)，求解为 Θ(nlog4 7).