algorithm - Q: 代入的递归关系

Question

我有递归关系：T(n) = c*T (n/3) + (c/2)*n 对于任何 c

让 T(n) >= n^1.5 作为替代方法的猜测。

标签： algorithmsubstitutionrecurrence

Answer 1

假设T(n) <= n^1.5是正确的道路。有了它，我们可以拥有：

T(n) <= 6 ( n^1.5 / 3^1.5 ) + 3n= (6 / 3^1.5)* n^1.5 + 3n。

6/3^1.5是 5.1 ......但现在让我们称之为a。所以我们有：a*n^1.5 + 3n。

我们需要证明对于 n0>n 存在 c > 0 c*n^1.5 > a*n^1.5 + 3n。首先让我们除以n：c*n^0.5 > a*n^0.5 + 3哪个产量：(c-a)*n^0.5 > 3。

从这里很明显你可以选择任何一个c > a， n > 9所以这将是真的。

总结一下：我们变得T(n)更大并T'(n) = (6/3^1.5)*n^1.5 + 3n证明了c > 6/3^1.5n > 9T(n) < cg(n) where g(n) = n^1.5