作者swon ()
看板Grad-ProbAsk
標題Re: [理工] [DS]-時間複雜度
時間Fri Jan 8 02:13:35 2010
※ 引述《doom8199 (～口卡口卡 修～)》之銘言：
: ※ 引述《yesa315 (XD)》之銘言：
: : T(n) = 3T(n/4) + nlog n 使用Θ表示
: : 2
: : 這有比較快速的算法嗎? 例如代換法??
: : 用暴力法求解我也求不太出來 有請高手給個方向
: : 謝謝!
: ---
: 令 T(n) + f(n) = 3[T(n/4) + f(n/4)]
: with f(n) = a*nlogn + b*n + c*logn + d
: → T(n) = 3T(n/4) + 3f(n/4) - f(n)
: = 3T(n/4) + (-a/4)nlogn - (3a/2 + b/4)n + 2c*logn + (2d-6c)
: 與原式比較係數後可得:
: ┌ (-a/4) = 1 ┌ a = -4
: │ 3a/2 + b/4 = 0 → │ b = 24
: │ 2c = 0 │ c = 0
: └ 2d-6c = 0 └ d = 0
: 所以 f(n) = -4nlogn + 24n ____(1)
: 因此 T(n) + f(n) = 3[T(n/4) + f(n/4)]
: = 3^[log_4 (n)] * [T(1) + f(1)]
: = n^(log√3) * [T(1) + f(1)]
: → T(n) = T(1)*n^(log√3) + f(1)*n^(log√3) - f(n)
: = T(1)*n^(log√3) + 24*n^(log√3) + 4nlogn - 24n
: or T(n) = Θ{ nlogn }
[挖以前的文章]
如果要純解題的話，你可以套下面這個方法，當然也是從 Master 定理整理出來的：
要訣就是在比大小就對了…大的就贏了 >////<
給題目： T(n) = aT(n/b) + f(n)
log a
b
Step 1：計算 n
Step 2：比較一下 Step 1 與 f(n) 值誰的複雜度大
則 T(n) = Θ(複雜度大的那個)
Step 3：Step 1 的值與 f(n) 的複雜度相同的話
則 T(n) = Θ( f(n) * lgn)
(多乘一個 lgn)
Step 4：處理一下例外情形，就是當 f(n) 比 Step 1 的值少 lgn 倍時。
不能使用 Master Theorem。
也就是說看到 f(n) 有 lgn 時就要小心一下就對了。
For Example
---------------------------------------------------------------------
T(n) = 3T(n/4) + nlog n
2
log 3
4
n < n log n
2
所以 T(n) = Θ(大的那個) = Θ(nlog n)
2
---------------------------------------------------------------------
T(n)=T(n/2)+O(1)
log 1
2
n = n^0 = 1 跟 f(n) 一樣
所以 T(n) = O(1) * lgn = Θ(lgn)
---------------------------------------------------------------------
T(n)=4T(n/2)+n
log 4
2
n = n^2 > n = f(n)
所以 T(n) = Θ(大的那個) = Θ(n^2)
---------------------------------------------------------------------
T(n) = 3T(n/4) + n
log 3
4
n < n = f(n)
所以 T(n) = Θ(大的那個) = Θ(n)
---------------------------------------------------------------------
T(n) = 2T(n/2) + n / lg n
log 2
2
n = n > n / lgn = f(n)
這時發現 f(n) 少了 lgn 倍，所以就不能套 Master Theorem了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.5.68
推 FRAXIS:最後一個可以用Master Theorem.. 01/08 09:39
感謝，修正了 XD
推 yesa315:f(n) 有log 不是要用extend master 嗎 01/08 13:24
→ yesa315:為什麼你用普通的Master Theorem就可以了!? 01/08 13:25
→ yesa315:n^log 4 3 =n^0=1不是嗎 要套用extend master也不行 01/08 13:26
→ yesa315:我的問題點就是在這裡 01/08 13:26
推 FRAXIS:n^(log 4 3)比nlg n小.. 01/08 17:32
推 yesa315:我了解了 觀念上得錯誤 謝謝Y 01/08 21:37
※ 編輯: swon 來自: 220.136.9.218 (01/09 02:09)