[理工] 110 台大 资演

楼主: jimmy1112111 (仔仔)   2022-01-12 02:31:25
https://i.imgur.com/ZDnToHr.jpg
有点疑惑C3和C4,对于C3我的想法是不能保证reduction是在O(n^3)完成,所以借由problem
B的算法设计出解problem A的算法,有可能不是O(n^3)只能说problemA可以在多项式时
间解决,因此C3倾向有误
而C4觉得有点纳闷,根据市面上的解答写说“使用解B的算法去设计解A的算法这个前提
下,若解A的算法为O(n^3),则可以设计出解B的算法也在O(n^3)解决”,但C4题目的假
设是A存在一个O(n^3)的算法,这并不能表示一定存在一个由解B的算法去组成的解A的演
算法,是在O(n^3),所以这个解答不太能接受。
大神是否有其他看法?
作者: foogty (夫葛踢)   2022-01-12 07:22:00
C3题目有写转换在linear time完成
作者: VF84 (Jolly Roger)   2022-01-12 07:45:00
C4 本来就是错的吧,我去年答案写 A,没被扣分。
作者: jacksoncsie (资工肥宅)   2022-01-12 08:39:00
我选 A
楼主: jimmy1112111 (仔仔)   2022-01-12 10:14:00
啧,我耍白痴了,谢以上几位Linear time reduction定义是在O(n)内reduction,所以保证problem A存在一个O(n^3)的算法由解problem B的算法组成

Links booklink

Contact Us: admin [ a t ] ucptt.com