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

作者: joywilliamjo (joywilliamjoy)   2020-11-26 10:48:05
https://i.imgur.com/eIXLFoo.jpg
想問一下第一題的counter example
完全沒有概念...
然後第二題的time complexity,儘管每一個set只含兩個
但一樣還是能得到approximation solution = O(logn)對嗎?
作者: CSGD (BinYu)   2020-11-26 15:47:00
X=(1,2,3,4,5,6), S=((1,2,3), (4,5,6), (1,2,5,6)) 因為greedy會先抓(1,2,5,6)

Links booklink

Contact Us: admin [ a t ] ucptt.com