[理工] 101 清大 計算機科學 計科 13題

看板Grad-ProbAsk作者 (joywilliamjoy)時間5年前 (2020/11/26 10:48), 5年前編輯推噓1(1推 0噓 3→)
留言4則, 1人參與, 5年前最新討論串1/1
https://i.imgur.com/eIXLFoo.jpg
想問一下第一題的counter example 完全沒有概念... 然後第二題的time complexity，儘管每一個set只含兩個 但一樣還是能得到approximation solution = O(logn)對嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.38.239 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1606358887.A.F75.html
→
11/26 15:47, 5年前 , 1F
X=(1,2,3,4,5,6), S=((1,2,3), (4,5,6), (1,2,5,6)) 因為
11/26 15:47, 1F
→
11/26 15:47, 5年前 , 2F
greedy會先抓(1,2,5,6)
11/26 15:47, 2F
感謝，那時間複雜度是那樣嗎？ O(logn)的approximate ※ 編輯: joywilliamjo (42.74.38.239 臺灣), 11/26/2020 23:29:30
推
11/27 10:18, 5年前 , 3F
可以查查看minimum edge cover, 把有出現子集的點相連就會
11/27 10:18, 3F
→
11/27 10:18, 5年前 , 4F
是同一個問題,有polynomial time演算法
11/27 10:18, 4F
‣ 更多 joywilliamjo 的文章
文章代碼(AID): #1VlnTdzr (Grad-ProbAsk)