作者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
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