作者gamed (Maiko)
看板Grad-ProbAsk
标题[理工] [资结]-master theorem
时间Fri Jan 22 21:10:16 2010
T(n) = 2 T( n/2 ) + n
看起来像是可以用老大定理
我看洪杰笔记:
老大定理:
令 f(n) = n 找一个ε > 0
使得 f(n) = O (n^log 2 - ε) => T(n) = θ (n^log 2) -----(1)
2 2
或 f(n) =Ω (n^log 2 + ε) => T(n) = θ (f(n)) -----(2)
2
可是我找不到 适合ε的值
ε= log 2 - 0.5 代 (1) 不行
2
ε= 1.5 - log 2 代 (2) 不行
2
哎...老大定理不熟 有没有大大可以教我一下...
我可以仿洪逸的写法吗?
by master theorem
因为
n^log 2 = n^1 , f(n) = n
2
所以 f(n) = θ (n^log 2)
2
=>T(n) = θ(n * lg n) <=log 2 = 1 不是应该等於 θ (n) 才对吗?
2
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.46.164.151
2F：推 taitin:ε=0的时候 是 θ[(n^lg2)*logn] 01/22 23:16
3F：→ tureday:老大定理遇到相等的直接补个logn 01/23 00:51