本文主要是介绍算法分析与设计 —— NP完全性理论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
确定性算法和非确定性算法
（1）确定性算法：整个执行过程中每一步都只有一个选择，则称A是确定性算法。对同样的输入，输出结果一定相同。
（2）非确定性算法：在每一时刻，根据当时的状态和输入，若机器有多个动作可供选择，第一个获得结束的成功选择使算法终止，此时称算法为非确定性的。
P类问题
用一个确定性算法在多项式时间内可解的问题。
（1） P类问题是NP问题的子集（如果P类问题既然能在多项式时间内求解，也必然能在多项式时间在验证它的解）
NP类问题
能在多项式时间内验证得出一个正确解的问题。
（1）对于哈密尔顿回路问题，如果给出一个任意的回路，我们可以很容易的判断出该回路是否是哈密尔顿回路（看是不是所有顶点都在回路中)，故哈密尔顿回路是NP问题。
约化
（1）一个问题A可以约化成问题B的含义即是，可以用解决问题B的解法来解决问题A，或者说，问题A可以“变成”问题B。如：一元一次方程可以“约化”为一元二次方程
（2）问题A可“约化”为问题B的直观意义：B的时间复杂度高于或等于A的时间复杂度。也就是说，问题A不比问题B难
（3）约化具有传递性：如果问题A可约化成问题B，问题B可约化成问题C，则问题A一定可约化成问题C
（4）约化需要在多项式时间内完成
<
这篇关于算法分析与设计 —— NP完全性理论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
