[理工] 110 台大 資演
有點疑惑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://www.ptt.cc/bbs/Grad-ProbAsk/M.1641925887.A.BB4.html
推
01/12 07:22,
3年前
, 1F
01/12 07:22, 1F
推
01/12 07:45,
3年前
, 2F
01/12 07:45, 2F
推
01/12 08:39,
3年前
, 3F
01/12 08:39, 3F
→
01/12 10:14,
3年前
, 4F
01/12 10:14, 4F
→
01/12 10:21,
3年前
, 5F
01/12 10:21, 5F
→
01/12 10:21,
3年前
, 6F
01/12 10:21, 6F
→
01/12 10:21,
3年前
, 7F
01/12 10:21, 7F