algorithm - 具有函数 nlogn 的主定理

Question

我们最近在学习中接到任务，用主定理解决递归函数的复杂性。我知道这些问题在这里被问了很多，但我无法从这些问题中找出这个问题的答案。特别是一个问题很好地描述了问题:here

我的问题是递归函数 T(n) = 5*T(n/3) + n *log(n)。如另一个问题所述，这应该可以用第二种情况解决(或非官方的第四种情况，它们非常相似)。但是，我找不到 f(n) = nlogn with a =5 and b = 3 的 Big-Theta。

非常感谢您的帮助。

Answer 1

如果我们能证明 f(n) = n log n = O(n^(log_3 5-\epsilon))

就可以用 Master 定理解决这个问题

如果成立，则结果遵循主定理的第一种情况

T(n) = Θ(n^(log_3 5))

看到那个；

• 取lim (n log n)/n^(log_3 5))
• evaluate log_3 5 ~ = 1.4649..
• substruct some epsilon = 0.0049...>0,
• lim (n log n)/n^(1.46)
• 取消n的
• 限制 log n/n^(0.45) = 0 并接受第一个医院
• 限制 n^(0.54)/(n * 0.46) =0