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

[joywilliamjo (joywilliamjoy)]

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
→ CSGD: X=(1,2,3,4,5,6), S=((1,2,3), (4,5,6), (1,2,5,6)) 因為
→ CSGD: greedy會先抓(1,2,5,6)
感謝，那時間複雜度是那樣嗎？
O(logn)的approximate
※ 編輯: joywilliamjo (42.74.38.239 臺灣), 11/26/2020 23:29:30
推 CSGD: 可以查查看minimum edge cover, 把有出現子集的點相連就會
→ CSGD: 是同一個問題,有polynomial time演算法