algorithm - 通过主定理找到递归方程的闭端公式

Question

我们能解决这个问题吗 T(n) = 2T( n/2 ) + n lg n recurrence equation master theorem 我来自一个链接，他说我们不能在这里应用主定理，因为它不满足任何 3ree 案例条件。另一方面，他举了另一个例子T(n) = 27T(n/3) + Θ(n^3 lg n) 并找到封闭解 theta(n^3logn ) 为了解决这个问题，他使用了主定理的第二种情况如果 f(n) = Θ(nlogba (lg n)k ) 那么 T(n) ∈ Θ(nlogba ( lg n)k+1) for some k >= 0 这里我的困惑出现了，为什么我们不能在这里应用第二种情况，而它完全适合第二种情况。我的想法: a = 2 , b =2;让 k = 1 那么 f(n) = theta(n^log_2 2 logn) for k= 1 所以 T(n) = theta(nlogn) 但是正如他提到的那样我们不能应用主定理我很困惑为什么不。

注意:这是由于 T(n) = 2T( n/2 ) + n lg n 中的 f(n) bcz f(n ) = nlog n 并且在 T(n) = 27T(n/3) + Θ(n^3 lg n) *f(n) = theta(n^3log n)* 如果我在这里错了，请纠正我。

Answer 1

使用主定理的情况 2 我发现

 T(n) = Theta( n log^2 (n))

您的链接指出 theroem 的情况 2 是:

 f(n) = Theta( n log_b(a))

虽然来自其他几个链接，例如 one from mit ，情况是:

 f(n) = Theta( n log_b(a) log_k(n)) for k >= 0