[理工] 演算法 時間複雜度
作者: suspect1 2018-01-03 14:21:00
Cormen ch4-4 b
T(n) = 5T(n/5) + n/lg n
我的解法:
T(n) = 5T(n/5) + n/lg n
= 25T(n/25) + 5*(n/5)/lg (n/5) + n/lg n
i=lg n
=5^i*T(n/5^i) + Σ [ n/(lg n -ilg 5)]
i=0
令n/5^i = 1 得 i=lg n (以5為底)
接下來不會處理後面的sigma了，求解
答案是 θ(n lglg n)
T(n) = 5T(n/5) + n/lg n
我的解法:
T(n) = 5T(n/5) + n/lg n
= 25T(n/25) + 5*(n/5)/lg (n/5) + n/lg n
i=lg n
=5^i*T(n/5^i) + Σ [ n/(lg n -ilg 5)]
i=0
令n/5^i = 1 得 i=lg n (以5為底)
接下來不會處理後面的sigma了，求解
答案是 θ(n lglg n)
作者: s1020824 (HowardW) 2018-01-03 14:28:00
答案是O(nloglogn)吧1/1+1/2+1/3+...+1/n=1/(log n)
作者: suspect1 2018-01-03 14:36:00
還是不懂s大的意思
作者: s1020824 (HowardW) 2018-01-03 14:45:00
" target="_blank" rel="nofollow">作者: suspect1 2018-01-03 14:53:00
瞭解，謝謝s大