作者jimmy1112111 (jxu)
看板Grad-ProbAsk
标题[理工] 110 台大 资演
时间Wed Jan 12 02:31:25 2022
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)，所以这个解答不太能接受。
大神是否有其他看法？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 113.61.200.52 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1641925887.A.BB4.html
1F：推 foogty: C3题目有写转换在linear time完成 01/12 07:22
2F：推 VF84: C4 本来就是错的吧，我去年答案写 A，没被扣分。 01/12 07:45
3F：推 jacksoncsie: 我选 A 01/12 08:39
4F：→ jimmy1112111: 啧，我耍白痴了，谢以上几位 01/12 10:14
5F：→ jimmy1112111: Linear time reduction定义是在O(n)内reduction， 01/12 10:21
6F：→ jimmy1112111: 所以保证problem A存在一个O(n^3)的演算法由解pro 01/12 10:21
7F：→ jimmy1112111: blem B的演算法组成 01/12 10:21