[演算法] 問題。急－dlxpxv7的部落格

標題:

[演算法] 問題。急

發問:

1. Given the recurrence relation T(n)=7T+(n/5)+10n 對於n>1 T(1)=1 請找到T(625)。＊須算出exact value; 非order 2. Using the definitions of O and Ω, show that 6n^2+20n ? (屬於類似E) O(n^3) but 6n^2 + 20n 不屬於 Ω(n^3)

最佳解答:

1. (您的題目打錯了吧?) 我把題目改成 T(n)=7T(n/5)+10n 對於 n>1 T(1)=1 既然只求 T(625), 所以直接疊帶最方便: T(625) = 7T(125)+10*625 = 7(7T(25)+10*125)+6250 = 7(7(7T(1)+10*25)+1250)+6250 = 7(7(7*1+250)+1250+6250 = (請您自己算此值) 2. (1) 6n^2+20n 是 O(n^3), 證明: 6n^2+20n <= 6n^3, for all n >= 3, 得證. (2) 6n^2+20n 不是 Ω(n^3), 證明: 當 n 趨近 infinity 時, (n^3)/(6n^2+20n) 會趨近於 infinity (微積分教的). 所以, 只要 n 夠大時, 6n^2+20n <= cn^3, for any c>0. 所以, 找不到一個 c>0, 使得 n 夠大時, 滿足 6n^2+20n >= cn^3, 因此 6n^2+20n 不是 Ω(n^3)