recurrence - 如何使用大师方法解决这种复发？

Question

T(n)=4t(n/2) + n^2 和 t(1)=1

我不知道伙计们，我可以解决其他问题，但我似乎卡住了，无法从这个开始

Answer 1

让我们完成这个，看看我们发现了什么。在这种情况下，我们有 a = 4、b = 2 和 d = 2。由于 log _b a = 2 = d，我们应该得到 t(n) = Θ(n ² log n)。

让我们通过考虑树中每个级别完成了多少工作来快速检查是否是这种情况。在顶层，我们做 n ^{2 个}工作，然后对大小为 n/2 的问题进行四次调用。这些问题中的每一个都可以 (n/2) ² = n ² / 4 工作，并且由于该问题有四个副本，因此在下一个级别完成的工作是 n ²。这些子问题中的每一个都会触发大小为 (n/4) ² = n ² / 16 的问题的四个递归调用，并且由于这些子问题中有 16 个，在该级别完成的工作也是 n ²。总的来说，我们看到树中的每一层都做了 n ²工作，并且有 Θ(log n) 层，所以完成的总工作是 Θ(n² log n)，匹配我们从主定理的界限。