作者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/m.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