[理工] 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