递归关系主定理

Question

T(n) = 6T(n/3) + n * (n-1)
T(1) = 4

如果我们有像上面这样的递归关系，我们应该怎么办？

   --> a*T(n/b) + f(n)
   --> a*T(n/b) + O(n^d)
   --> 6*T(n/3) + O((n^2) - n)
   --> 6*T(n/3) + O(n^2)

似乎我们应该使用 O(n^d)。如果我们通过这种方式，结果是 O(n^2).

但我不能确定。好像少了点什么。任何人都可以帮助判断这种方式是否正确，如何逐步解决这个问题？提前致谢。

Answer 1

我认为您可以继续将定理应用于下一步：

$T(n) = 6T(\frac{n}{3}) + n * (n-1)$

$T(n) = 6T(\frac{n}{3}) + O(n^{C})$ $c = 2$

$\rightarrow T(n) = O(N^{2})$

根据主定理的第一个通用形式：wikipedia

Recurrence Relation Master Theorem