我很難理解和解決重復關系。有人可以幫我解決這個問題嗎？T(n)=T(n/3) T(2n/3) n
uj5u.com熱心網友回復：
看看這張圖片：
這是一個你可以繼續的遞回樹。
另外，就像我在 URL 中找到的那樣：
到葉子的最短路徑發生在我們每次取重分支時。
將 k 視為樹結果的高度：
(pow(n*(1/3),k) ≤ 1)意味著 k ≥ lg3 n。
到葉子的最長路徑發生在我們每次取光分支時。
將 k 視為樹結果的高度：
(pow(n*(2/3),k) ≤ 1)意味著 k ≥ lg3/2 n。
現在看看這張圖片：
這意味著在任何完整級別上，n 的加法項的總和。
現在，讓我們看看我們有什么。
如果你選擇高度是
對數3
結果將是：
-
T(n) ≥ nlog3 n --> T(n) ≥ Ω (nlogn)
如果你選擇高度是
log3/2 n
結果將是：
-
T(n) ≥ nlog3/2 n --> T(n) ≤ O(nlogn)
這兩個（1和2）將引導我們T(n) = Θ(nlogn)
其他來源：幫助
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520466.html
標籤：算法时间复杂度复发
下一篇：如何從串列中獲取整數？