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

[mqazz1 (無法顯示)]

※ 引述《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:為什麼第一題可以這樣算啊?謝謝: )
我記得是某一年交大的考題 主要是在考這個定理= =
你可以稍微找一下洪捷的名校那本@@
→ gskman:因為他也是算到背起來
→ gskman:把tree畫一下，才比較清楚
※ 編輯: mqazz1          來自: 218.166.118.76       (01/20 20:59)
→ gskman:洪杰也是畫tree
推 okjn816:噢噢我懂了!!!謝謝!!!