你如何找到這樣的遞推關係的嚴格界限?這是一個重要的問題,我們期望證明m/log(m)是嚴格的漸近界。我嘗試使用感應,但它似乎無處可去。這是要麼我缺少對數規則或有更多的東西。復發T(n)= T(n - log(n))+ 1
0
A
回答
1
感應。假設所有k < n
的T(k) <= C k/log k
對於某些C
。
展開復發(n/2)/log(n/2)
次,更換log(.)
與log(n/2)
(我們利用的事實,即T(n)
和log(n)
是單調函數)。也就是說,
T(n) <= T(n - log(n/2) * (n/2)/log(n/2)) + (n/2)/log(n/2)
T(n) <= T(n/2) + (n/2)/log(n/2)
T(n) <= C (n/2)/log(n/2) + (n/2)/log(n/2)
現在你要證明右邊的表達被C n/log n
界。算術和找到這樣的C
是作爲一個練習。
相關問題
- 1. 復發:T(n)= T(n/2)+ log N
- 2. 復發:T(n)=(2 + 1/log n)T(n/2)
- 3. 複製關係:T(n/16)+ n log n
- 4. 的復發T(N)= 2T(N/2)+(N-1)
- 5. T(n-1)+ 1/lg(n)復發
- 6. 解決一個復發的關係T(N)= T(N-√N)+1
- 7. 求解:T(n)= T(n/2)+ n/2 + 1
- 8. 如何解決:T(N)= T(N - 1)+ N
- 9. T(n)的的漸近複雜= T(N-1)+ 1/N
- 10. 復發T(N)= T(N/3 + 5)+ T(2π/ 3 + 7)+ O(1)
- 11. 查找溶液復發:T(N)= 2 T(N/4 +√N)+(√10)N
- 12. T(n)= T(n - sqrt(n))
- 13. 中間體步驟T(N)= 2T(N/2)+ N /的log(n)
- 14. 如何解決復發A(n)= A(n-1)+ n * log(n)?
- 15. 確定重複關係的運行時間T(n)= T(n-1)+ n
- 16. 解決遞歸T(N)=日誌(T(N-1))+ 1
- 17. 解決T(n-1)+ sqrt(n)的復發問題
- 18. 如何解決T(N)= T(N-2)+ T(2)+ N遞歸樹
- 19. 如何解決這個複雜的等式,T(n)= T(n-3)+ T(n-5)
- 20. 問題解決復發T(n)= 4T(n/4)+ 3log n
- 21. 計算遞推關係T(N)= N + T(N/2)
- 22. inplace_merge:是什麼導致N * log(N)與N-1的複雜性?
- 23. 證明log(n!)是Ω(n log(n))
- 24. 是log(n!)= O((log(n))^ 2)?
- 25. 主定理,解決復發,T(N)= 3T(N/2)+ nlogn
- 26. 代碼O(nlog(n))的T(n)如何?
- 27. 如何從沒有/ n/t/t的xml文件中讀取myValue \ n \ t \ t
- 28. const boost :: array <T,N>或boost :: array <const T,N>?
- 29. 獲得每組最後[n,n + t]天
- 30. 解決復發問題:T(n)= 3T(2n/3)+1
告訴我們你如何開始歸納,也許有人可以從那裏幫助你。 – ShadowMitia