解決復發關係的時間複雜度？

Question

我正在做一個家庭作業的問題，需要我比較nlogn和下面的重複。至於nlogn是否低於，高於或者緊於下面的時間複雜度。

| 5    n = 1 
--| 2T(n/2) + n n > 1 

我覺得2T（N/2）+ N降低到nlogn但我不完全知道如何解決的遞推關係..

謝謝您的幫助。

Answer 1

解決復發（我希望我這樣做是正確的）：

2T(n/2) + n 
2[2T(n/4) + n/2] + n 
2^2*T(n/2^2) + 2n 
you find the pattern if you keep on substituting new n 
2^k*T(n/(2^k)) + kn 
at this point you solve for closed form using the base case then n = 1 
so for n/n = 1, we set 2^k = n, so k = logn 
sub in k 
2^(logn) * T(1) + (logn) * n 

note that 2^logn = n with base 2 and T(1) = 5 for the base case 
so we obtain 5n + nlogn 
5n + nlogn is just O(nlogn) 

既然我們都爲O（nlogn），它是一個嚴密的綁定或大西塔。

或者，您還可以使用主定理輕鬆地減去複雜性。如果你已經學會了。

a = 2 
b = 2 
c = 1 

滿足以上2的情況下，這是Θ（nlogn），指維基https://en.wikipedia.org/wiki/Master_theorem

Answer 2

簡答 - 您可以（也應該）使用「主定理」來找到此復發的O標記。

大師定理是一個方便的工具來解決復發，它應該是你的第一個選擇，因爲你可以很快得到結果。你可以得到一個動手本exercise