我有一個非常奇怪的函式，它看起來像這樣：
T(n) = 2T(n/2) n* log2(n)
我需要用替換方法來解決這個問題，但我一直無法得出任何決定性的答案。
我需要解決方案步驟和大 O
uj5u.com熱心網友回復：
面對時log，像n = 2^k( k = log2(n)) 這樣的改變往往是一種出路：
n = 2^k
所以我們有
T(2^k) = 2 * T(2^(k - 1)) k * 2^k
讓我們看看它是什么意思：
T(2^k) = 2 * T(2^(k - 1)) k * 2^k =
= 2 * (2 * T(2^(k - 2)) (k - 1) * 2^(k - 1)) k * 2^k =
= 4 * T(2^(k - 2)) (k - 1) * 2^k k * 2^k =
= 4 * (2 * T(2^(k - 3)) (k - 2) * 2^(k - 2)) (k - 1) * 2^k k * 2^k =
= 8 * T(2^(k - 3)) (k - 2) * 2^k (k - 1) * 2^k k * 2^k =
...
= 2^k * T(0) 2^k 2 * 2^k ... k * 2^k =
= 2^k * T(0) 2^k (1 2 ... k) =
= 2^k * T(0) 2^k * k * (k 1) / 2 =
= 2^k * (T(0) k * (k 1) / 2)
回傳時間n, n = log2(k):
T(n) = n * (T(0) log2(n) * (log2(n) 1) / 2)
就O(n)我們而言
O(T(n)) = O(n * (T(0) log2(n) * (log2(n) 1) / 2)) =
= O(n * (const log2(n)^2 / 2 log2(n) / 2) =
= O(n * log2(n)^2 / 2) =
= O(n * log2(n)^2) =
= O(n * log(n)^2)
所以，答案是
O(T(n)) = O(n * log(n)^2)
請注意，由于log2(n) == log(n, b) / log(2, b)對于任意基數，b > 1我們可以使用log(n)代替log2(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/363466.html
下一篇：添加到位元組而不會溢位