[理工] [DS]-時間複雜度
總共五小題，想看我有沒有算錯
一個配分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
推
01/10 16:00, , 1F
01/10 16:00, 1F
→
01/10 17:59, , 2F
01/10 17:59, 2F
自問自答，用疊代法算出 nloglogn，不過我算好久，才2分@@
※ 編輯: polomoss 來自: 122.116.14.2 (01/10 19:20)
→
01/10 19:43, , 3F
01/10 19:43, 3F
討論串 (同標題文章)