我有一個回溯演算法。運行時間由以下關系給出：
T(n) = T(n - 1) T(n - 2) T(n - 3) T(n - 4) ... T(1)
T(1)=1
這個演算法最差的時間復雜度是多少？直覺上，它在我看來是 O(n^n)。但我可能錯了。如何正式計算？
uj5u.com熱心網友回復：
這是一個簡單的方法：您可以通過擴展每個加法項并觀察模式來計算時間復雜度：
T(n)
= T(n-1) T(n-2) T(n-3) 。 .. T(1)
= (T(n-2) T(n-3) ... T(1)) T(n-2) T(n-3) ... T(1)
= 2T(n-2) 2T(n-3) ... 2T(1)
= 4T(n-3) ... 4T(1)
= 2^(k- 1) T(nk) ... 2^(k-1) T(1)
= 2^(n-2) T(1)
= 2^(n-2)
uj5u.com熱心網友回復：
T(n) = (T(1) T(2) ... T(n-2)) T(n-1)
= T(n-1) T(n-1)
= 2T(n-1)
因此T(n) = c * 2^n，在c哪里T(1)/2。
uj5u.com熱心網友回復：
您有以下內容：
T(1) = 1
T(2) = T(2-1) = T(1) = 1
T(3) = T(3-1) T(3-2) = T(2) T(1) = 2
T(4) = T(4-1) T(4-2) T(4-3) = T(3) T(2) T(1) = 2 1 1 = 4
T(5) = 4 2 1 1 = 8
T(6) = 8 4 2 1 1 = 16
...
從上面可以得出結論T(n) = 2*T(n-1)，在基本情況下T(1) = T(2) = 1
我們可以進一步建立在這句話的基礎上，因為T(n) = 2*T(n-1)，T(n) = 2*2*T(n-2)。隨之而來的是T(n) = (2^i)*T(n-i)fori < n-2和n > 2。
所以就時間復雜度而言，我們得到O(2^n)。
注意：如果我錯了，請糾正我。我對這些東西不是最好的。我提前致歉。我正在努力學習自己。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/414606.html
標籤：