作者try66889 (猫猫只求黑琴ㄍㄟˋ婚 )
看板Grad-ProbAsk
标题[理工] 资演 交大105 (27)(60)
时间Tue Oct 20 20:21:15 2020
爬过板上的文惹不过还是有两小题不太懂想请问大家><
1.(Solved)
https://i.imgur.com/6U9SiY3.jpg
https://i.imgur.com/mhSLLXi.jpg
想请问这题的（c）选项 nlog*n 和 n^a 那边不知道要怎麽比较QQ
2.
https://i.imgur.com/uqtLyo4.jpg
主要想问E选项，不知道要怎麽改才正确
谢谢大家！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.32.191.76 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1603196477.A.C15.html
1F：推 NTUmaki: 多项式正数次方一定比log快 10/20 21:14
了解~ 感谢N大~
※ 编辑: try66889 (114.32.191.76 台湾), 10/20/2020 22:07:59
2F：推 mi981027: 2. 要把任意CNF转换成3CNF的形式有时候得引入额外变数 10/21 07:04
3F：→ mi981027: 举例，要把A v B转成3CNF，可以引入额外变数p 10/21 07:04
4F：→ mi981027: 变成(A v B v p) ^ (A v B v not(p)) 10/21 07:04
5F：→ mi981027: 概念其实就是引入一个没用的变数把他凑成3CNF 10/21 07:04
6F：→ mi981027: 这在CLRS证明3CNF是NP-complete时有提到(p. 1082) 10/21 07:04
了解惹OWO! 感谢m大~
※ 编辑: try66889 (114.32.191.76 台湾), 10/21/2020 12:51:27
※ 编辑: try66889 (114.32.191.76 台湾), 10/22/2020 11:56:35