[理工] 103台大DS 對答案

[ssssIssss (O_O)]

以下是我的答案,1,2,4題想麻煩各位大大一起討論～

1.
(a)T(n)=c*(2^(loglogn))+(loglogn)*(logn)
       =O(loglogn*logn)

(b)T(n)=O(n) --> 此處我是暴力做個一兩輪，找出幾個項的最大值保留，其餘
刪去，最後得出O(n)

(c)T(n)=1/n + 1/(n-1) + ... + 1
       =O(logn)

2.
(a.)C k 取 i

(b.)root有最大degree, k

4.
用greedy之方式，每次往權重最小的邊走，每走一步記錄下經過多少thick跟
thin，並算出總共的總重，若到達F時還沒滿足k,n則退回走另一條，若滿足
k或n則之後皆走另一種edge。



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483696283.A.5D8.html
※ 編輯: ssssIssss (140.112.25.99), 01/06/2017 17:54:30
→ w181496: 4.無法用greedy
→ w181496: 簡單舉個反例： http://i.imgur.com/finRw6s.jpg
→ w181496: 假設都是thin邊 求走2個thin邊的最短路 你的方法會得到10
→ w181496: 01
了解，所以要用DP慢慢疊上去？
※ 編輯: ssssIssss (111.243.101.221), 01/08/2017 20:49:19
推 cyc4542015: 2.b 他是問n個node的最大degree 所以答案應該是lgn?
→ ssssIssss: 是的