[理工] 台大103,成大102 103 演算法 複雜度計算

[h04mp6286 (H28)]

台大103的第1題的第2小題

  T(n) = T(n/2 + √n) + n

  這題我真的沒有想法,用recursion-tree弄出一大推奇奇怪怪的東西

成大102的計算題的第1小題

  T(n) = 2T(n/2) + n/lgn

  這題我看T○B的名校攻略上寫是O(nlglgn)

  想請問是怎麼來的我已經知道每層是n/(-i+lgn)了

  要怎麼把n/(-i+lgn)化成O(nlglgn)啊

還有成大103第2題想跟大家對下

我寫:若M極大:T(n)=M              :O(1)

       M極小:T(n)=16T(n/2)+Θ(1) :O(n^4)

可是感覺有點怪怪的,想參考神人們的寫法看看

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.110.239
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422435383.A.9A1.html
推 kather: 2. recur tree 弄出來是 n(1/1+1/2+...+1/lgn)=nlglgn
→ kather: 最後我覺得是O(n^4)..
推 drink1004: 成大那題用extended master method就可以解決了，如果
→ drink1004: 我沒弄錯的話
→ drink1004: 補充一下是成大102第一小題
推 galapous: 不能用吧@@  他不符合條件
推 hbkhhhdx2006: 成大102那題就令n=2^k，然後用疊代
推 drink1004: 噢我看錯了不要理我哈
→ h04mp6286: 超感謝hbkhhhdx2006大提供一個超棒的想法啊
→ h04mp6286: 有人有台大那題的想法嗎?
→ AdvenRal: 用substitution method去證T(n)=O(n)
推 FRAXIS: 用 Akra-Bazzi method 帶進去得到Θ(n)
推 Billgaspeed: 我們老師是說直接省略根號n 就直接解出來了