我正在嘗試使用迭代方法解決重復問題。我知道解決方案應該是 θ(n^2) 但我無法用迭代方法解決它。
這是我走了多遠：
- T(n) = 4T(n/2) n
- T(n) = 4(4T(n/4) n/2) n
- T(n) = 4(4(4T(n/8) n/4) n/2) n
我不知道如何計算總和。我希望有一個人可以幫助我。
提前致謝！
uj5u.com熱心網友回復：
讓我們k這樣定義2^k = n（^代表上臺）。所以我們有
T(n) = 4 * T(n / 2) n
作為
T(2^k) = 2^2 * T(2^(k-1)) 2^k
讓我們放松一下：
T(2^k) = 2^2 * T(2^(k-1)) 2^k =
= 2^4 * T(2^(k - 2)) 2^(k 1) 2^k =
= 2^6 * T(2^(k - 3)) 2^(k 2) 2^(k 1) 2^k =
= 2^8 * T(2^(k - 4)) 2^(k 3) 2^(k 2) 2^(k 1) 2^k =
...
= T(0) * (2^(2 * k) ... 2^(k 2) 2^(k 1) 2^k) =
= T(0) * (2^k * (2^k 2^(k - 1) ... 4 2 1)) =
= T(0) * (2^k * (2 * 2^k - 1))
是時候從k回到n; 因為我們有2^k = n：
T(n) = T(0) * n * (2 * n - 1)
有了接近的公式，T(n)我們可以很容易地計算θ：
θ(T(0) * n * (2 * n - 1)) =
= T(0) * θ(n * (2 * n - 1)) =
= 2 * T(0) * θ(n^2) =
= θ(n^2)
uj5u.com熱心網友回復：
您可以通過與您所做的相同的方式輕松地對其進行近似：
T(n) = 4T(n/2) n
T(n) = 4(4T(n/4) n/2) n = 4^2 T(n/4) 2n n
T(n) = 4(4(4T(n/8) n/4) n/2) n = 4^3 T(n/8) 4n 2n n
|--first part--|--second part--|
起初，由于每次迭代減半，因此此迭代發生log(n)在最大值處。
現在對于第一部分，在i轉之后是4^i，所以它將來自O(4^log(n)) = O(n^2)。
對于第二部分，它是一個幾何系列n 2n 4n 8n.... n*2^i=n*(2^(i 1)-1)。所以它的攤銷時間log(n)為O(n*2^log(n))=O(n^2)。
由于這兩部分都是O(n^2)，并且它們相加，所以總的攤銷時間也是O(n^2)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/410216.html
標籤：
上一篇：使用聯合查找回傳正確數量的島嶼
下一篇：如何在C 中列印剩余的一組數字？