主定理，解決復發，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...)