NP-hard是什么意思

  算法/数据结构/数据库 计算复杂度    浏览次数:7803        分享

NP-hard到底是什么意思?我不是学计算机的,但是遇到了这个概念。有没有简单一点的解释,网上的意思都好复杂。


多谢!

 

Sophia   2017-02-28 00:34



   1个回答 
12

P:能够以多项式时间被求解的问题称为P-问题。比如说O(n),O(n^5),这都是多项式时间。

举个例子,给n个数,找出其中所有的偶数。这个就是P-问题。


NP:首先NP-问题不能以多项式的时间求解;并且,如果我们假设找到了一个答案,这个答案可以以多项式的时间检验该答案是否正确。

比如说,我们要找出所有(1,2,3)的置换,并且第一个元素小于第二个元素。这里一共有3!=3*2*1=6个置换,(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1),符合第一个元素小于第二个元素的置换有3个。如果是(1,2,...,n)的置换,我们则需要至少O(n!)的时间来求解,这是大于多项式时间的。再者,如果给出任意一个备选答案,比如(5,2,1,4,3),我们只需要花多项式的时间(这里是O(n)时间)来检查这个备选答案是不是真的是一个置换并且第一个元素小于第二个元素。


NP-hard:首如果一个问题通过一些步骤能够化简为一个NP问题,那么这个问题就是NP-hard问题。换句话说,至少是NP的问题称之为NP-hard问题。

著名的NP-hard例子就是旅行商问题。假设有n个城市,找出一条每个城市都访问一次且仅访问一次的最短路线。


SofaSofa数据科学社区DS面试题库 DS面经

可爱多   2017-02-28 09:51

给力 - 雕牌   2017-02-28 12:07
感谢大神! - Sophia   2017-03-01 09:46


  相关主题

beam search是什么意思?   1回答

sql查询时count(*)、count(1)、count()哪个更快?   1回答

在python中获取模型运行的时间   3回答

kNN进行预测时计算复杂度是多少?   1回答

朴素贝叶斯的训练/预测效率如何?快吗?   1回答

1000个瓶子和10个小白鼠的算法题   1回答

Python Packaging 的最佳实践?   1回答

python中怎么获取cpu的个数?   1回答

python的set进行append操作?   2回答

怎么在python中复制指定路径下的文件?   1回答

python中如何合并两个dict   2回答

python中defaultdict的用法   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!