[理工] 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

继续阅读