主定理扩展案例

Question

谁能给我解释一下？

我有这个案例：

T(n) = 3*T(n/3) + n*logn

为什么这个案例是主定理案例二而不是三？

Answer 1

我们有，根据wikipedia notation：

a = 3
b = 3
c = log_b(a) = 1

这符合情况 2：f(n) = n log n = n^(c = log_b(a) = 1) log n

它不适合情况 3，因为 f(n) 不是 big-omega(n^k)，其中 k > c = 1（我稍微更改了维基百科符号以免重新定义 c ).

例如，n^1.1 不是 n log n 的下限可能不是很明显，但是 n^1.1 is actually a bigger value 足够大 n .