推 taitin:ε=0的時候 是 θ[(n^lg2)*logn] 01/22 23:16
→ tureday:老大定理遇到相等的直接補個logn 01/23 00:51
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