3
A
回答
2
經過一些想法我不能想出一個精確解。師父的定理在這裏不起作用,展開樹沒有給我任何合理的東西。所以我只是用以下方式來估計複雜性。
對於任何合理的大n
你可以估計0 < 1/log n < 1
。所以你可以得到:
T1(n) = 2 * T1(n/2)
T2(n) = 3 * T2(n/2)
and O(T1) < O(T) < O(T2)
。您可以使用master theorem找到兩次重複的複雜性。 T1
的複雜度爲O(n)
,而T2
的複雜度爲O(n^log2(3))
。
因此,您可以確定您的復發複雜度大於O(n)
且小於O(n^1.58)
,因此小於二次方。
相關問題
- 1. 復發:T(n)= T(n/2)+ log N
- 2. 查找溶液復發:T(N)= 2 T(N/4 +√N)+(√10)N
- 3. 的復發T(N)= 2T(N/2)+(N-1)
- 4. 復發T(n)= T(n - log(n))+ 1
- 5. 求解:T(n)= T(n/2)+ n/2 + 1
- 6. 如何解決T(N)= T(N-2)+ T(2)+ N遞歸樹
- 7. 復發T(N)= T(N/3 + 5)+ T(2π/ 3 + 7)+ O(1)
- 8. 解決一個復發的關係T(N)= T(N-√N)+1
- 9. T(n)= T(n - sqrt(n))
- 10. T(n-1)+ 1/lg(n)復發
- 11. 計算遞推關係T(N)= N + T(N/2)
- 12. 如何解決:T(N)= T(N - 1)+ N
- 13. 複製關係:T(n/16)+ n log n
- 14. T(n)的的漸近複雜= T(N-1)+ 1/N
- 15. 主定理,解決復發,T(N)= 3T(N/2)+ nlogn
- 16. 如何解決這個複雜的等式,T(n)= T(n-3)+ T(n-5)
- 17. 問題解決復發T(n)= 4T(n/4)+ 3log n
- 18. 中間體步驟T(N)= 2T(N/2)+ N /的log(n)
- 19. 確定重複關係的運行時間T(n)= T(n-1)+ n
- 20. 如何解決如$ T(n)= T(n/2)+ T(n/4)+ O(m)這樣的遞歸關係$
- 21. 解決T(n-1)+ sqrt(n)的復發問題
- 22. 如何從沒有/ n/t/t的xml文件中讀取myValue \ n \ t \ t
- 23. 無法從轉換 'T [N] [2]' 到 'T [] [2]'
- 24. const boost :: array <T,N>或boost :: array <const T,N>?
- 25. 解決遞歸T(N)=日誌(T(N-1))+ 1
- 26. 問題:T [] b =(T [])new Object [n];
- 27. std ::查找類型T ** vs T * [N]
- 28. 代碼O(nlog(n))的T(n)如何?
- 29. 獲得每組最後[n,n + t]天
- 30. 大O和T(N)混淆