Re: [理工] [資結] 簡單的big-oh問題協助

看板Grad-ProbAsk作者mqazz1 (無法顯示)時間14年前 (2012/01/20 20:29)推噓2(2推 0噓 3→)

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

※ 引述《okjn816 (蔡包)》之銘言： : 1.請問T(n)=T(n/3)+T(n/6)+n的big-oh要怎麼算啊?? : 答案上說用recursive tree來解，可是沒說細節。 1/3 + 1/6 = 1/2 < 1 => O(n) : 2.請問T(n)=2T(n/2)+n/logn 一樣要麼求big-oh? 先change variable 令 m = lgn => n = 2^m m m-1 m T(2 ) = 2T(2 ) + 2 /m m 令 S(m) = T(2 ) m S(m) = 2S(m-1) + 2 /m = ... m m = 2 S(0) + 2 ( 1/1 + 1/2 + ... + 1/m) m = O(2 lgm) lgn = O(2 lglgn) = O(nlglgn) 有錯請指證要是演算法都考這種題目就好了=..= : 我被這種題目困擾好久了感覺應該很簡單希望各位大大能幫忙謝謝!!!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.166.118.76

推

okjn816

01/20 20:44, , 1^F

01/20 20:44, 1^F

我記得是某一年交大的考題主要是在考這個定理= = 你可以稍微找一下洪捷的名校那本@@

→

gskman

01/20 20:53, , 2^F

01/20 20:53, 2^F

→

gskman

01/20 20:55, , 3^F