[理工] 103台大DS 對答案

看板Grad-ProbAsk作者ssssIssss (O_O)時間9年前 (2017/01/06 17:51)推噓1(1推 0噓 5→)

留言6則, 3人參與討論串1/1

以下是我的答案,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

01/07 23:47, , 1^F

01/07 23:47, 1^F

→

w181496

01/07 23:47, , 2^F

01/07 23:47, 2^F