2013-02-18 124 views
0

復發的運行時間是什麼T(n)=3T(2n/3)+1以及您是如何得到它的?解決復發問題:T(n)= 3T(2n/3)+1

+1

我們不是做你的功課你。至少要說明你的失敗分析結果如何,我們會盡力幫助解決這個問題。但是現在,你可能只是在說謊「陷入困境」,在上面的問題中輸入是迄今爲止唯一付出的努力。 – 2013-02-18 22:22:54

+0

我一直堅持了不到一個星期,並在一個點上,我在這裏發佈堆棧溢出,並且包括我的嘗試(在這裏:http://stackoverflow.com/questions/14888827/trouble-trying-to對的一復發-find最漸近的運行時)。沒有人迴應,所以我想我會再試一次。 – 2013-02-18 23:15:42

回答

0

使用Master Theorem。這比試圖解決復發問題要容易得多,就像你在原始問題中嘗試過的那樣。

OTTOMH這應該得到你T(n) = Theta(n^2.7)(主定理的情況1)。

1

這種類型的重複可以用Master theorem來解決。這裏a=3,b=3/2f(n) = 1。您的c = log1.5(3) = 2.709而且因爲n^2.709大於f(n),您將陷入第一種情況。

因此,解決辦法是O(n^2.709)