recurrence - 求解复杂的递归关系

Question

如何解决以下递归关系？

T(n) = 2T(root(n)) + logn/loglogn if n > 4
T(n) = 1 if n <= 4

最好通过主定理，否则通过任何方法。我知道 Master Theorem 失败了，但是这些类型的问题是否有任何扩展？你能指导我解决上述复杂关系的任何东西吗？

Answer 1

我认为这应该有效：

如果 n = 2^m 并且 T(2^m) = s(m) 那么

logn = m , loglogn = logm ;

s(m) = 2*s(m/2) + m/logm ;

现在解决上面的方程是我们的问题现在你不能使用主定理来解决这个问题，所以你必须使用其他方法，比如通过写 s(m/2) 和 s(m/4) 来扩展这个方程，然后你可能解决这个问题，然后再将参数更改为 n 。

Answer 2

据我说

如果 n = 2^m 并且 T(2^m) = s(m) 那么

logn = m , loglogn = logm ;

s(m) = 2*s(m/2) + m/logm ;