作者doom8199 (～口卡口卡 修～)
看板Grad-ProbAsk
標題Re: [理工] [DS]-時間複雜度
時間Thu Jan 7 23:30:56 2010
※ 引述《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 }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.151
推 polomoss:這種解法一直看不懂@@ 01/07 23:33
→ doom8199:你可以先想比較簡單的問題: T(n) = 3T(n/4) 01/07 23:47
→ doom8199:若要解出 T(n) 的 closed form , 要如何下手? 01/07 23:47
※ 編輯: doom8199 來自: 140.113.141.151 (01/08 01:33)
推 FRAXIS:其實這解法蠻有趣的 但是f(n)要怎麼猜? 01/08 09:43
→ FRAXIS:f(n)的可能有非常多種..有甚麼系統化的猜法嗎? 01/08 09:45