主定理 f(n) = nlogn

Question

我正在处理算法导论第 3 版中的问题 4-3。我被要求找到 T(n) 的渐近上限和下限：

T(n) = 4T(n/3) + n lg(n)

我在网上浏览了解决方案，解决方案说：

By master's theorem, we get T(n) ∈ Θ(n^log₃(4))

我相信解决方案假设 n^log₃4 渐近大于 n lg(n)？但为什么是这样呢？如果有人能帮助我理解，我将不胜感激！

Answer 1

通俗地说：

我们需要比较 n*log(n) 和 n^1.25 (log3(4)~1.26)

的增长

将两个函数除以 n

  log(n) vs n^(1/4)

两者都在增加。
两个函数的导数

  n^(-1)  vs n^(-3/4)

第二个的导数明显更大，所以第二个函数增长得更快

We can see 这些函数的图相交并且幂函数对于大 n 值变得更大 - 对于 any power>1

master theorem f(n) = nlogn