[理工] 102成大程設 oao521 PTT批踢踢實業坊

作者: oao521 (台灣金正日) 2020-02-09 22:01:19

想請問這一題
https://i.imgur.com/SbLsXdQ.jpg
這一題題目不太明白在敘述什麼?
還有圈起來的符號(下標)是指什麼意思呢?

作者: ok8752665 (dd8752665) 2020-02-09 22:04:00

請看演算法 np那章

作者: oao521 (台灣金正日) 2020-02-09 22:06:00

啊當兵完演算法都忘光了而且我演算法也讀一點點而已好我再去研究一下演算法謝謝大大剛剛去翻了一下NP-complete那章想請問看完那一章就可以明白這一題的觀念嗎?np那一章在後半段這題在資結第一章所以我先略過嗎?

作者: gash55025502 (白影弓) 2020-02-09 22:18:00

圈起來的那個符號可以想成想成P1的難度小於等於P2又P2屬於p 因此P1也屬於p因為對lglgn取lg得lglgn*lglglgn<lgn 因此lglgn屬於多項式等級

作者: tyjason0509 (小翔) 2020-02-09 23:31:00

是再加上一點時間複雜度的概念就會懂了

作者: Kedge (0.0) 2020-02-10 10:32:00

p1可以使用polynomial time的演算法reduce到p2

繼續閱讀