Re: [理工] [DS]-時間複雜度

看板Grad-ProbAsk作者doom8199 (～口卡口卡　修～)時間16年前 (2010/01/08 14:19)推噓5(5推 0噓 6→)

留言11則, 4人參與討論串7/17 (看更多)

-- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.141.151

推

polomoss

01/07 23:33,

01/07 23:33

→

doom8199

01/07 23:47,

01/07 23:47

→

doom8199

01/07 23:47,

01/07 23:47

※ 編輯: doom8199 來自: 140.113.141.151 (01/08 01:33)

推

FRAXIS

01/08 09:43,

01/08 09:43

→

FRAXIS

01/08 09:45,

01/08 09:45

賺一下 p 幣XD 假設 T(n) = a*T(n/b) + f(n) 若想把上式改寫成 T(n) - k(n) = a[T(n/b) - k(n/b)] 那得去 try k(n) 的型態其實要分兩個 case 討論: <1> 直接由 f(n) 型態下去 try: ex: T(n) = 3T(n/4) + nlogn 因為要合併成 T(n) - k(n) = 3[T(n/4) - k(n/4)] 所以就同時考慮 k(n) 、 k(n/4) 也就是假設 k(n) 可由 nlogn 、 (n/4)log(n/4) 組成這時若把 (n/4)log(n/4) 稍微整理一下會得到 (n/4)log(n) - (n/2) 此時會發現 k(n) "也必須要有 n 這個項" 這時我們在重新假設: k(n) 可由 nlogn 、 (n/4)log(n/4) 、 n 、 (n/4) 組成相當於 k(n) 可以由 nlogn 、 n 組成到這步就等於可以 try k(n) = a*nlogn + b*n <2> 由 (logn)^r*f(n) 型態下去 try: (其中 r屬於R) ex: T(n) = 2T(n/2) + n 這種 case 比較討厭因為若直接照第一種 case 的流程去想會變成: 假設 k(n) 型態可由 n 、 (n/2) 組成表示可以直接假設 k(n) = a*n 可是當帶回原式: T(n) + a*n = 2[T(n/2) + a*(n/2)] → T(n) = 2T(n/2) → GG ---- 第二種 case 會爆的原因其實很簡單由 T(n) = 2T(n/2) 可解出通解 T(n) = T(1)*n 會發現特解的型態跟齊性解相衝有學工數的人應該對這句話再熟悉不過XD 若假設的特解型態和齊性解有重疊我們會如何去修正特解的假設方式 ? O.D.E. 的處理方式，跟解遞迴式完全一樣 ! 就是改假設新的特解為 k(n)' = (logn)*k(n) ps: 可以想想為何要乘上 (logn)^r 來修正 ---- 回到 case 2 的 example 假設 k(n) = a*nlogn 則: T(n) + a*nlogn = 2[T(n/2) + a*(n/2)log(n/2)] → T(n) = 2T(n/2) + an 比較係數後可得 a = 1 即特解為 k(n) = nlogn ------------------------------------------------------------------------------ 其實 master theorem 本身就是一種 try 解的方式只是演算法相對上比較重視最高 order 那個項所以就沒有像我這樣直接把通解都求出來XD 若我們假設 T(n) = a*T(n/b) + f(n) 其通解為 T(n) = T(1)*T(n)_c + T(n)_p ^^^^^^ ^^^^^^ 齊性解特解 master theorem 它是直接比較 T(n)_c 、 T(n)_p 、 f(n) 這三者的 order 所以才會分那麼多 case XD ( 會比較 f(n) 是因為想判斷有沒有和齊性解的型態重疊 ) 算是題外話 OTZ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.141.151

推

FRAXIS

01/08 15:06, , 1^F

01/08 15:06, 1^F

→

doom8199

01/08 15:23, , 2^F

01/08 15:23, 2^F

→

doom8199

01/08 15:30, , 3^F

01/08 15:30, 3^F