[理工] Time complexity, NP

看板Grad-ProbAsk作者 (羅密歐與豬過夜)時間5年前 (2018/12/27 11:19), 編輯推噓2(2推 0噓 9→)
留言11則, 3人參與, 5年前最新討論串1/2 (看更多)
想請問版上各位幾題， https://i.imgur.com/fMTSPKA.jpg
以上幾題是F,F,T 想請教這一題的概念是什麼，這一題的概念是很單純的比較嗎...？ 還是說可以用reduce 的概念去想呢？以此概念來想的話就是，B reduces 到A所以A比B難 。 因為跟林立宇的答案不太一樣QQ 麻煩各位大大幫忙了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.73.184 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545880793.A.D35.html
推
12/27 13:49, 5年前 , 1F
第一題如果帶A=O(n^2)就不成立，所以False，第二題帶A
12/27 13:49, 1F
→
12/27 13:49, 5年前 , 2F
=O(1)就不成立，所以False，第三題因爲nlogn<n^2，所
12/27 13:49, 2F
→
12/27 13:49, 5年前 , 3F
以如果要B>n^2的話代表A一定要>n^2，所以True
12/27 13:49, 3F
→
12/27 15:15, 5年前 , 4F
第一題如果用reduce 的想法去想，B如果本身O(n) 可以解
12/27 15:15, 4F
→
12/27 15:15, 5年前 , 5F
，只是為了用A解所以reduce到A花了O(nlogn) 那麼怎麼能
12/27 15:15, 5F
→
12/27 15:15, 5年前 , 6F
肯定B就是O(lower bound of A)?
12/27 15:15, 6F
→
12/27 15:17, 5年前 , 7F
同樣的，A也可能可以reduce到B，但...題目給的是B reduc
12/27 15:17, 7F
→
12/27 15:17, 5年前 , 8F
es 到A, 所以我假設A比B難，不知道這樣能不能QQ 謝謝W大
12/27 15:17, 8F
→
12/27 15:17, 5年前 , 9F
的回答
12/27 15:17, 9F
推
12/27 23:42, 5年前 , 10F
我在想老師會不會是用若p則q的等價命題非q則非p看這題
12/27 23:42, 10F
→
12/27 23:43, 5年前 , 11F
如果用reduce的看法寫這題我會寫F F F吧
12/27 23:43, 11F
‣ 更多 eggy1018 的文章
文章代碼(AID): #1S94JPqr (Grad-ProbAsk)
‣ 更多 eggy1018 的文章
文章代碼(AID): #1S94JPqr (Grad-ProbAsk)