作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
标题[理工] 101 清大 计算机科学 计科 13题
时间Thu Nov 26 10:48:05 2020
https://i.imgur.com/eIXLFoo.jpg
想问一下第一题的counter example
完全没有概念...
然後第二题的time complexity，尽管每一个set只含两个
但一样还是能得到approximation solution = O(logn)对吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.74.38.239 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1606358887.A.F75.html
1F：→ CSGD: X=(1,2,3,4,5,6), S=((1,2,3), (4,5,6), (1,2,5,6)) 因为11/26 15:47
2F：→ CSGD: greedy会先抓(1,2,5,6)11/26 15:47
感谢，那时间复杂度是那样吗？
O(logn)的approximate
※ 编辑: joywilliamjo (42.74.38.239 台湾), 11/26/2020 23:29:30
3F：推 CSGD: 可以查查看minimum edge cover, 把有出现子集的点相连就会 11/27 10:18
4F：→ CSGD: 是同一个问题,有polynomial time演算法 11/27 10:18