復發，主或置換方法複雜性計算

-5

下面給出了五種算法的遞推方程。假設所有這些算法都解決了同樣的問題。你會推薦哪一個？爲什麼？爲了回答上述問題，您需要找到所有算法的漸近效率。然後您需要比較的不同效率以確定最有效的算法。復發，主或置換方法複雜性計算

I. ALGORITHM 1 : T(n) = T(n-2) + n 
II. ALGORITHM 2 : T(n) = 4T(n/2) + n2 lg n + 100 log n 
III. ALGORITHM 3 : T(n) = T(3n/4) + 2n – 4 
IV. ALGORITHM 4 : T(n) = 3T(n/2) + 2n ln n + 10n 
V. ALGORITHM 5 : T(n) = 2T(n/4) + √ + 10 lg n

對於所有算法假定T（0）= T（1）= 1。可以使用您選擇的方法來解決的復發。

P.S真的需要幫助解決它，它將不勝感激。提前致謝。

來源

2014-11-03 KailashExchage

我們不是在這裏做你的功課，你嘗試過什麼遠嗎？ – Michael 2014-11-03 17:00:50

是的，我已經嘗試過，最後只是混亂。 @Michael – KailashExchage 2014-11-03 17:43:46

查看下面的答案 – Michael 2014-11-03 17:44:07

只是點U在正確的方向：

T(n-2) + n 
= T(n-4) + n - 2 + n = T(n-4) +2n - 2 
= T(n-6) + n - 4 + 2n -2 = T(n-6) + 3n - 6

假設n爲偶數和T（0）= 1

所以我們最終

T(n) = (n/2)*n - sum [from i=0 to (n/2)-1] (i) 
    = (n/2)*n - [(n/2)*(n/2-1)]/2 +1

這應該是在O（n²）（它很久以前，因爲我做了那些事情，所以不能保證）

來源

2014-11-03 17:03:58 Michael

復發，主或置換方法複雜性計算

回答

相關問題