加载中…
个人资料
xyzitime
xyzitime
  • 博客等级:
  • 博客积分:0
  • 博客访问:13,048
  • 关注人气:1
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

什么是NP问题,什么有是NP完全问题(NP-complete problem)

(2012-07-03 16:04:48)
标签:

算法

杂谈

np

p

分类: 离散数学

在算法复杂度分析的过程中,人们常常用特定的函数来描述目标算法,随着变量n的增长,时间或者空间消耗的增长曲线,近而进一步分析算法的可行性(有效性)。

引入了Big-O,Big-Ω,来描述目标算法的上限、下限复杂度函数。
用Big-Θ描述和目标函数同序的复杂度函数,即由Big-Θ既是上限也是下限。

常常用到如下时间复杂度函数标度

1,  log n,  n,  n log n,   n^2,  2^n,  n!

通常将具有n^x,x为正整数形式的时间复杂度函数称为多项式复杂度。通常认为具有多项式时间复杂度的算法是容易求解的。超过多项式时间复杂度,算法增长迅速,不易求解。

下图将展示NP和NP完全问题在所有问题中的位置。

什么是NP问题,什么有是NP完全问题(NP-complete <wbr>problem)

通常问题分为 可解决(Solvable)不可解决(Unsolvable)

可决绝问题又可以分为 易解决(Tractable)不易解决(Intractable)不确定是否容易解决(NP)

可解决(Solvable)是指存在算法能够解决的问题

不可解决(Unsolvable)是指不存在解决该问题的算法,如The Halting Problem。


易解决(Tractable),即P问题,是指具有最坏时间复杂度为多项式时间的算法能够解决的问题

不易解决(Intractable)是指不存在最坏时间复杂度为多项式时间的算法能够解决的问题

不确定是否容易解决(NP),还未被证明是否存在多项式算法能够解决这些问题,而其中NP完全问题又是最有可能不是P问题的问题类型。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有