我该如何使用主方法解决这种递归问题？
T(n) = 4T(n/2) + n2 + logn
我不知道如何着手解决它，但我很确定可以使用主方法来解决。我是否需要忽略其中一个术语？任何帮助都将不胜感激，谢谢。
1个回答
5
主定理适用于可以写成以下形式的函数：
T(n) = aT(n / b) + f(n)
在本例中，a = 4，b = 2，f（n）= n² + log n。请注意，我们将“ n² + log n”作为f（n）项分组，而不是将其视为两个单独的项。
现在，我们可以直接应用主定理。注意，logb a = log2 4 = 2，并且f(n) = Θ(n²)，因此根据主定理，这解决为Θ(n² log n)。之所以有效，原因是n² + log n = Θ(n²)，而主定理仅关心f（n）的渐近复杂度。实际上，任何这些递归都可以以相同的方式解决。
希望这可以帮助您！
T(n) = aT(n / b) + f(n)
在本例中，a = 4，b = 2，f（n）= n² + log n。请注意，我们将“ n² + log n”作为f（n）项分组，而不是将其视为两个单独的项。
现在，我们可以直接应用主定理。注意，logb a = log2 4 = 2，并且f(n) = Θ(n²)，因此根据主定理，这解决为Θ(n² log n)。之所以有效，原因是n² + log n = Θ(n²)，而主定理仅关心f（n）的渐近复杂度。实际上，任何这些递归都可以以相同的方式解决。
希望这可以帮助您！
- templatetypedef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接