申请试用
HOT
登录
注册
 
NP-Completeness

NP-Completeness

乐乐
/
发布于
/
1898
人观看
本章节主要介绍了计算机的NPC问题,这个主题的经典参考是计算机和难以理解的书:Michael Garey和David Johnson,1979年的NP-Completeness理论指南。几乎所有问题到目前为止所讨论的可以通过具有形式O(nk)的最坏情况时间复杂度的算法来解决,对于k的某个固定值,其与输入大小n无关。通常k很小,比如2或3.例子包括最短路径(SP),最小生成树(MST),排序,LCS,矩阵链乘法等。这些算法被认为是“有效的”,因为随着问题规模的增大,它们的性能会逐渐降低(多项式)。因此,在形式O(nk)时可解决的问题(并且自然地)是多项式可解的,并且被称为易处理的。
0 点赞
0 收藏
0下载
相关文档
确认
3秒后跳转登录页面
去登陆