作者jameschou (DOG)
看板Grad-ProbAsk
標題Re: [理工] [DS]-代入法..
時間Sat Nov 13 09:37:27 2010
※ 引述《bernachom (Terry)》之銘言：
: 不好意思，請教一題小問題
: 題目是
: T(n)=3T(√n)+logn , #log以10為底
: 經過推算之後，找到n應該用2k代入logn裡面
: 可是因為以10為底...變得不太會算..
: 還麻煩前輩教導一下了
: 謝謝幫忙
先不用管他以幾為底
先帶入就是了
1/2
T(n) = 3T(n ) + logn
1/4 1/2 2 1/4
= 3(3T(n )+log(n ))+logn = 3 T(n )+logn+(3/2)logn
= ...
k 1/2^k
= 3 T(n ) + logn + (3/2)logn + (9/4)logn + ... + (3/2)^(k-1)logn
k 1/2^k logn((3/2)^k-1)
= 3 T(n ) + -----------------
(1/2)
k 1/2^k
= 3 T(n ) + 2logn((3/2)^k-1) ......(1)
設T(2) = 1
1/2^k
要讓 n = 2 ,兩邊取log => (1/2^k)log n = 1
2 2
k
=> log n = 2 , 兩邊再取log => log log n = k 代回剛剛的(1)
2 2 2 2
log log n log log n
2 2 2 2
=> T(n) = 3 + 2logn(3 /log n -1)
2
如果你本來那個log是以2為底 那上面等式的最右邊那項比較好消
log n
2
就算是以10為底也可以化成 -------- 來消, 但基本上寫到這邊就可以了
log 10
2
如果是要求big O
loglogn
那答案就是 O(3 ) , big O的話以誰為底就沒差了.
loglogn log3 logb loga
3 也可以寫成 logn (因為a = b )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.83
※ 編輯: jameschou 來自: 140.113.139.83 (11/13 09:49)
推 bernachom:好清楚，謝謝您，不過我好像...說太快了，如果一定要變 11/13 10:40
→ bernachom:數變換呢?? 11/13 10:40
→ bernachom:謝謝您詳細的幫忙和解說 11/13 10:41
推 mqazz1:感覺先令m=logn 再令S(m)=T(10^m) 接著套master比較快XD 11/13 15:16
→ mqazz1:題目漏看 原來有規定用帶入法解= = 11/13 15:21
→ jameschou:照樓上說的那種假設方法 之後再用代入法 會得到跟我本來 11/13 20:11
→ jameschou:這篇代入後式子差不多的式子 然後再代回去就可以了 11/13 20:11
→ jameschou:你可以自己試試看 動手寫一寫很好觀察的! 11/13 20:12
推 bernachom:我等一下來寫寫看，謝謝嚕^^ 11/13 20:22
推 bernachom:想到一件事情...這題不能用master... 11/13 20:26
→ bernachom:推出來是F(k)=3^k F(0)+k*k ?? 感覺怪怪的... 11/13 20:28
推 bernachom:一直忘記回，之後我算出來了，謝謝^^ 11/14 22:52
→ jameschou:恩恩恭喜:) 11/15 20:14