[理工] 資演 交大105 (27)(60)

[try66889 (貓貓只求黑琴ㄍㄟˋ婚 )]

爬過板上的文惹不過還是有兩小題不太懂想請問大家><

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1603196477.A.C15.html
推 NTUmaki: 多項式正數次方一定比log快
了解~ 感謝N大~
※ 編輯: try66889 (114.32.191.76 臺灣), 10/20/2020 22:07:59
推 mi981027: 2. 要把任意CNF轉換成3CNF的形式有時候得引入額外變數
→ mi981027: 舉例，要把A v B轉成3CNF，可以引入額外變數p
→ mi981027: 變成(A v B v p) ^ (A v B v not(p))
→ mi981027: 概念其實就是引入一個沒用的變數把他湊成3CNF
→ mi981027: 這在CLRS證明3CNF是NP-complete時有提到(p. 1082)
了解惹OWO! 感謝m大~
※ 編輯: try66889 (114.32.191.76 臺灣), 10/21/2020 12:51:27
※ 編輯: try66889 (114.32.191.76 臺灣), 10/22/2020 11:56:35