具有函数 nlogn 的主定理
Master Theorem with function nlogn
我们最近在学习中接到任务，用主定理解决递归函数的复杂性。我知道这些问题在这里被问了很多，但我无法从这些问题中找出这个问题的答案。
特别是有一个问题很好地描述了问题：here
我的问题是递归函数T(n) = 5*T(n/3) + n *log(n)。
如另一个问题所述，这应该可以用第二种情况解决（或非官方的第四种情况，它们非常相似）。
但是，我找不到 f(n) = nlogn with a =5 and b = 3.
的 Big-Theta
非常感谢你的帮助。
如果我们能证明 f(n) = n log n = O(n^(log_3 5-\epsilon))
就可以用大师定理解决这个问题
如果成立则结果来自主定理的第一种情况
T(n) = Θ(n^(log_3 5))
看到那个；
- 拿
lim (n log n)/n^(log_3 5))
- evaluate log_3 5 ~ = 1.4649..
- substruct 一些 epsilon = 0.0049...>0,
lim (n log n)/n^(1.46)- 取消 n 的
limit log n / n^(0.45) = 0 去第一医院limit n^(0.54)/(n * 0.46) =0
我们最近在学习中接到任务，用主定理解决递归函数的复杂性。我知道这些问题在这里被问了很多，但我无法从这些问题中找出这个问题的答案。 特别是有一个问题很好地描述了问题：here
我的问题是递归函数T(n) = 5*T(n/3) + n *log(n)。
如另一个问题所述，这应该可以用第二种情况解决（或非官方的第四种情况，它们非常相似）。
但是，我找不到 f(n) = nlogn with a =5 and b = 3.
非常感谢你的帮助。
如果我们能证明 f(n) = n log n = O(n^(log_3 5-\epsilon))
如果成立则结果来自主定理的第一种情况
T(n) = Θ(n^(log_3 5))
看到那个；
- 拿
lim (n log n)/n^(log_3 5)) - evaluate log_3 5 ~ = 1.4649..
- substruct 一些 epsilon = 0.0049...>0,
lim (n log n)/n^(1.46)- 取消 n 的
limit log n / n^(0.45) = 0去第一医院limit n^(0.54)/(n * 0.46) =0