我们能解决这个问题吗T(n) = 2T( n/2 ) + n lg n递推方程主定理我来自一个环节，他说我们不能在这里应用主定理，因为它不满足3ree情形的任何条件。另一方面，他又举了一个例子
为了解决这个问题，他使用了主定理的第二种情况，我产生了困惑，为什么我们不能在这里应用第二种情况，而它完全适合第二种情况。
我的想法：A=2，B=2；那么让K=1
f（n）=θ（n^log 2 logn），对于k=1，t（n）=θ（nlogn），但他在这里提到，我们不能应用主定理，我很困惑为什么不能。
注意：这是由于f（n）bcz在T(n) = 27T(n/3) + Θ(n^3 lg n)theta(n^3logn)和If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0*T(n) = 2T( n/2 ) + n lg n*请纠正我这里的错误。
最佳答案
利用主定理的情况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