復發的運行時間是什麼T(n)=3T(2n/3)+1
以及您是如何得到它的?解決復發問題:T(n)= 3T(2n/3)+1
0
A
回答
0
使用Master Theorem。這比試圖解決復發問題要容易得多,就像你在原始問題中嘗試過的那樣。
OTTOMH這應該得到你T(n) = Theta(n^2.7)
(主定理的情況1)。
1
這種類型的重複可以用Master theorem來解決。這裏a=3
,b=3/2
和f(n) = 1
。您的c = log1.5(3) = 2.709
而且因爲n^2.709
大於f(n)
,您將陷入第一種情況。
因此,解決辦法是O(n^2.709)
相關問題
- 1. 解決類似復發:T(N)= 3T(N/3)+ N/3
- 2. 主定理,解決復發,T(N)= 3T(N/2)+ nlogn
- 3. 解決T(n-1)+ sqrt(n)的復發問題
- 4. 解決一個復發的關係T(N)= T(N-√N)+1
- 5. 問題解決復發T(n)= 4T(n/4)+ 3log n
- 6. 如何解決:T(N)= T(N - 1)+ N
- 7. 復發T(n)= T(n - log(n))+ 1
- 8. 解決復發T(n)= T(n/2)+ lg n?
- 9. 復發關係T(n)= T(n ^(1/2))+ T(nn ^(1/2))+ n
- 10. T(n-1)+ 1/lg(n)復發
- 11. 解決遞歸T(N)=日誌(T(N-1))+ 1
- 12. 明確的復發公式:T(n)= 2 * T(n - 1)+ 4^n + 1
- 13. 復發關係:T(n)= T(n - 1)+ n - 1
- 14. 的復發T(N)= 2T(N/2)+(N-1)
- 15. 如何解決復發A(n)= A(n-1)+ n * log(n)?
- 16. 求解:T(n)= T(n/2)+ n/2 + 1
- 17. 遞推關係:解決T(N-1)
- 18. 復發T(N)= T(N/3 + 5)+ T(2π/ 3 + 7)+ O(1)
- 19. 復發:T(n)=(2 + 1/log n)T(n/2)
- 20. iBatis的如何解決更復雜的N + 1個問題
- 21. 復發關係:T(n)= T(n/2)+ n
- 22. 使用主定理求解重複T(n)= T(n/2)+ O(1)?
- 23. T(n)的的漸近複雜= T(N-1)+ 1/N
- 24. 如何解決這個複雜的等式,T(n)= T(n-3)+ T(n-5)
- 25. 復發:T(n)= T(n/2)+ log N
- 26. T(N)= T(N-1)+ 10/N
- 27. 遞歸的複雜性:T(n)= T(n-1)+ T(n-2)+ C
- 28. 如何解決T(N)= T(N-2)+ T(2)+ N遞歸樹
- 29. 如何解決遞歸複雜度T(n)= T(n/4)+ T(3n/4)+ cn
- 30. T(n)=(T(n-1)+ n!)的時間複雜度是多少?
我們不是做你的功課你。至少要說明你的失敗分析結果如何,我們會盡力幫助解決這個問題。但是現在,你可能只是在說謊「陷入困境」,在上面的問題中輸入是迄今爲止唯一付出的努力。 – 2013-02-18 22:22:54
我一直堅持了不到一個星期,並在一個點上,我在這裏發佈堆棧溢出,並且包括我的嘗試(在這裏:http://stackoverflow.com/questions/14888827/trouble-trying-to對的一復發-find最漸近的運行時)。沒有人迴應,所以我想我會再試一次。 – 2013-02-18 23:15:42