主定理，解决复发，T（N）= 3T（N/2）+ nlogn

Question

T（N）= 3 * T（N/2）+ N *的log（n）

这种情况下，应被应用，为什么？我认为案例1但不确定。

主定理：

Answer 1

T(n) = 3 * T(n/2) + n * log(n) 

a = 3/b = 2/f(n) = n log n 

n^(log_b(a-ep)) = n^(log_2(3-ep)) = n^1.58... 

f(n) = n log n and is in O(n^1.58) as in case (1) 

Therefore, T(n) in Theta(n^1.58...)