[理工] 算法第六章习题 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

[理工] 算法 第六章习题

[理工] 算法第六章习题