[理工] [DS]-時間複雜度

[polomoss (小澤)]

總共五小題，想看我有沒有算錯
一個配分2分，

題目有一句敘述:Assume that T(n) is constant for sufficiently small n



a)T(n) = 3T(n/2) + nlogn

→直接帶master，算出θ(n^log 3)
                            2


b)T(n) = 5T(n/5) + n/logn

→疊代法，算出θ(nloglogn)


c)T(n) = T(3n/4) + T(n/5) + n

→畫TREE，得θ(n)


d)T(n) = 3T(n/3 + 5) + n/2

→這題不會算，我是省略+5，可是題目給足夠小n
  是否代表不能省略? 省略後得θ(nlogn)


e)T(n) = n^1/2 T(n^1/2) + n^1/2

→這題完全沒頭緒@@



謝謝

--
 學長學長!那邊有飆車族    學長學長!那邊剛好像有女生   學長學長~那邊有人紅燈右轉
         砍人                   被壓上車                                ψQSWEET
    鴿  ◥        鴿  ◥    鴿  ◥          鴿  ◥        鴿  ◥他媽的◤  鴿   
 ◤◎ ◎ 喔~~  ◤︶ ︶   ◤◎ ◎   喔~~  ◤︶ ︶       ◤◎ ◎ 攔下來呀!⊙ ⊙◥ 
 ◥    ◤      ◥  █◤  ◥    ◤        ◥   3◤╯ξ  ◥    ◤沒王法了◥皿  ◤
 ◥ ◥◥ (哈欠)◤ ◥◤   ◥ ◥◥   (煙~) ◤ ◥ ◤￣    ◥ ◥◥是不是?!(◥ ◤ ◤)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.14.2
推 FRAXIS:(b)是不能代Master Theorem的 (e)兩邊同除n再用代換法
→ polomoss:b)帶完左邊n比右邊大~不能這樣比嗎?
自問自答，用疊代法算出 nloglogn，不過我算好久，才2分@@
※ 編輯: polomoss        來自: 122.116.14.2         (01/10 19:20)
→ polomoss:感覺n/lgn就會比n小，但是居然等於nlglgn，真奇妙