[理工] 演算法第六章習題 magic83v PTT批踢踢實業坊

[理工] 演算法第六章習題

作者: magic83v (R7) 2018-12-28 15:12:07

https://i.imgur.com/64j8gs5.jpg
https://i.imgur.com/dmWKFay.jpg
想確認一下
第一題F是因為最差還有階乘時間嗎
註1:npc在sub exponential 解決是定理
註3:3-sat不可在sub exponential 解決
這邊是什麼意思
第二題True
時間複雜度就是指upper bound？
感謝

作者: rockieloser (友善大隊長) 2018-12-28 15:18:00

下限很難證吧

作者: w199381 (噁心肥宅) 2018-12-28 15:27:00

時間複雜度可以是任何asymptotic notation 只是上限是比較容易證明的且容易比較再去確認定義後好像也不對QQ 別理我

作者: sdfg014025xx (隨便就好) 2018-12-28 18:22:00

1. 沒有特別說過NPC的問題worst case 是在指數吧 2我的理解是通常估算時間複雜度都是想知道上限

作者: JKLee (J.K.Lee) 2018-12-28 20:15:00

如果證出任一題NPC一定不能在polynomial time內解出那就代表P不等於NP但是目前無人能證出到底P=NP還是P!=NP所以第一題是false

繼續閱讀

[理工] 計組 Pipeline 的Control signalsjojoboy0115 [理工] 線代第七章AAQ8 [理工] 計組cache問題ok8752665 [理工] 演算法時間複雜度 Amotized costcschenptt [理工] 離散 chessboard 6-78jojoboy0115 [理工] pipelined datapathMarcolod Re: [理工] Time complexity, NPJKLee [理工] 計組 byte offset定義！Aa841018 107成大資管資結JocMon [理工] 計組p20......!Aa841018

[理工] 演算法 第六章習題

[理工] 演算法第六章習題