算法设计与分析什么是P问题、NP问题和NPC问题.ppt

NP问题 我说我RP人品运气)很好肯定能随便给你指条很短的路出来然后我就胡乱画了几条线说就这条吧那人按我指的这条把权值加起来一看嘿神了路径长度98比100小于是答案出来了存在比100小的路径 别人会问他这题怎么做出来的他就可以说因为我找到了一个比100 小的解 在这个题中找一个解很困难但验证一个解很容易验证一个解只需要O(n)的时间复杂度也就是说我可以花O(n)的时间把我猜的路径的长度加出来 那么