Re: [理工] [DS]-代入法..

看板Grad-ProbAsk作者jameschou (DOG)時間15年前 (2010/11/13 09:37)推噓5(5推 0噓 11→)

留言16則, 4人參與討論串2/2 (看更多)

※ 引述《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, , 1^F

11/13 10:40, 1^F

→

bernachom

11/13 10:40, , 2^F

11/13 10:40, 2^F

→

bernachom

11/13 10:41, , 3^F

11/13 10:41, 3^F