作者doom8199 (～口卡口卡 修～)
看板Grad-ProbAsk
標題Re: [理工] [DS]-時間複雜度
時間Fri Jan 8 14:19:04 2010
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.151
1F：推 polomoss:這種解法一直看不懂@@ 01/07 23:33
2F：→ doom8199:你可以先想比較簡單的問題: T(n) = 3T(n/4) 01/07 23:47
3F：→ doom8199:若要解出 T(n) 的 closed form , 要如何下手? 01/07 23:47
※ 編輯: doom8199 來自: 140.113.141.151 (01/08 01:33)
4F：推 FRAXIS:其實這解法蠻有趣的 但是f(n)要怎麼猜? 01/08 09:43
5F：→ FRAXIS:f(n)的可能有非常多種..有甚麼系統化的猜法嗎? 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
6F：推 FRAXIS:那我想知道 這種猜法針對Master Theorem不能套用的題目 01/08 15:06
7F：→ doom8199:可以舉幾個例子嗎 @@? 01/08 15:23
8F：→ doom8199:不過若 master thm. 都不能套，表示特解大家都湊不出來 01/08 15:30
9F：→ doom8199:那要叫我湊，應該也會卡死XD 01/08 15:31
10F：推 FRAXIS:T(n) = 2T(n/2) + n/logn 像這種 01/08 17:15
11F：→ doom8199:這個型態我 try不出特解QQ , 可能要用無窮級數下去算 01/09 00:21
12F：→ doom8199:然後再看無窮級數能不能寫成 closed form 01/09 00:22
13F：推 polomoss:好難...短時間吸收不了@@ 01/09 00:36
14F：推 FRAXIS:我之前有整理過不能套用的題目類型 #1AFR6-r7 01/09 07:21
15F：→ FRAXIS:答案應該是O(nlglgn) 01/09 07:21
16F：推 yesa315:也可以用遞廻樹解 01/09 10:31