作者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/m.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