[理工] 演算法

[f111222003 (lai1003)]

http://imgur.com/spgdmRg

想請問一下這題的第一小題

我覺得是T 但答案是F

謝謝大家

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.150.166
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1452005649.A.0E1.html
推 goldflower: 知道A的下限只能規定B的上限吧?
推 irenelove: 題意是B可在nlogn的時間ruduce到A
→ irenelove: 所以A的難度大於等於B
→ irenelove: 既然B比A簡單 他的lower bound就有可能比A的更小
推 forever3580: 單從題目給的限制來看 他只有規定上限 但是 沒有對下
→ forever3580: 限做限制 因此即使B的下限是n 甚至到常數等級都是可
→ forever3580: 以的