recursion - T(n)=2T(n/2) + n*log(logn) 的解

Question

我正在努力解决这个等式。我得出结论，主定理不适用于这种情况，因此我尝试连续替换这些项以求解该方程，但无法继续。有人能告诉我解决这个问题的最佳方法是什么吗？

谢谢

Answer 1

正如您推断的那样，由于情况三的条件失败，我们不能使用主定理。

但首先我们有 n^(log_b a) = n(log_2 2) = n

现在 n < n* log(log(n))

因此，与其他项 n*(log(log n)) 相比，递归项 2T(n/2) 的贡献不断减少……因此我们现在可以忘记该项……

现在考虑术语 n(log(log n))

扩大重复，但我们重视这个术语，我们有，

T(n) = 2^k * T(n/2^k) + n [ log(log(n/2^(k-1))) + log(log(n/2^(k-2)) .....]

把 2^k 作为我们的 n，

T(n) =忽略第一项+ n [ log(log(2)) + log(log(4)) +.....+ log(log(2^(k-1))) ]

T(n) =忽略第一项+ n [ log(1) + log(2) + log(3) +......+ log(k-1) ]

T(n) =忽略第一项+ n [ log((k-1)!) ]

我们只需要一个上限，因此我们可以利用斯特林近似，

嗯！< (n/e)^n

因此（k-1）！~ ((k-1)/e)^(k-1)

因此 log((k-1)!) = (k-1)[(log(k-1) - log (e)]

但是 k = log n => [ log((k-1)!) ] = (log(n) - 1) [log(log(n)-1 - log(e)]

因此我们的术语 n [ log((k-1)!) ] = n*log(n)*log(log(n)) 和一些我们可以忽略的低阶术语..

因此答案是：O(n*log(n)*log(log(n)))

PS：我不确定这个答案，请检查并告诉我是否犯了一些错误！