Re: [理工] [DS]-時間複雜度
※ 引述《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
推
01/07 23:33, , 1F
01/07 23:33, 1F
→
01/07 23:47, , 2F
01/07 23:47, 2F
→
01/07 23:47, , 3F
01/07 23:47, 3F
※ 編輯: doom8199 來自: 140.113.141.151 (01/08 01:33)
推
01/08 09:43, , 4F
01/08 09:43, 4F
→
01/08 09:45, , 5F
01/08 09:45, 5F
討論串 (同標題文章)