算法的时间复杂度指的是算法计算所需要的数量级，通常用O(·)表示。
O(1)表示一个算法是常数阶，例如访问HashMap的某一个元素（随机存取）只需要一次运算即可。
O(n)表示一个算法是线性阶，例如寻找数组Array中最大的元素，需要遍历数组（顺序表）的所有元素。
O(logn)是对数阶，比O(n)更快，例如有序表的二分查找。
O(n^2)表示一个算法是平方阶，例如冒泡排序算法对数组进行排序。
O(nlogn)介于O(n)和O(n^2)之间，常见的有快速排序、归并排序算法。
以上都是多项式级别的复杂度，即O(n^a)以下。
下面的是非多项式级别，更难计算。
O(a^n)是指数级递增的计算规模。例如常见的“汉诺塔问题”，就是2^n次计算。
O(n!)复杂度的是阶乘规模的算法，例如一组数的全排列。
如果一个问题可以找到一个能在多项式时间内解决的算法，称为P问题(polynomial)。
NP问题：可以在多项式时间内验证问题的一个可能解（non-deterministic polynomial）。
所谓P=NP？就是讨论，是否所有NP问题都是P类问题（显然所有P问题都是NP问题，能找到算法自然可以轻松验证。）
一个复杂度较低的问题，可以约化（Reducibility）为复杂度较高的问题，例如一次方程可以视为二次项系数为0的二次方程。
NPC是指NP完全问题，可以在多项式时间内验证问题的一个可能解，但是要找到问题的解通常需要高于多项式的时间。1. NPC问题是一个NP问题。2. 所有的NP问题都可以约化为NPC问题。
NPC的性质：NP虽然可以快速验证，但是没有任何数据结构和算法可以在多项式时间内解决NPC；所有已知的NPC问题都可以用图论的形式表示出来；如果一个问题被归约到某个NPC问题，就可以认为它也是个NPC问题。
其不可能有多项式级复杂度的算法。只要任意一个NPC问题找到了多项式算法，那么所有的NP问题就都可以用该算法去解决了，即证明了P=NP。（其实恰恰是NPC问题的存在让人们相信P不等于NP）。当前的NPC问题通常只能用指数级别甚至阶乘级别复杂度的算法求解。
逻辑电路问题：给定一个逻辑电路，问是否存在一种输入使得该电路输出为True。该问题已被证实为NPC问题，并且任意一个NP问题都可以约化为逻辑电路问题。
NPC问题其他案例：TSP（Traveling Saleman Problem 旅行商问题）、背包问题、图着色问题、布尔可满足性问题（SAT Boolean Satisfiability Problem）、子集和问题等。计算理论、集合论、图论等领域都发现越来越多NP问题，对NPC问题深入研究可以设法克服这些问题。
证明一个问题是NPC问题。首先证明其是一个NP问题，然后用一个已知的NPC问题进行多项式时间的规约。
NP-Hard问题不一定是NP问题，也可能是非NP问题。但所有NP问题都可以约化为NP-Hard问题。P属于NP，NP和NP-Hard的交集为NPC。NP-Hard问题同样很难找到多项式算法。
标签：多项式,复杂度,NPC,问题,算法,笔记,NP From： https://www.cnblogs.com/zhaoke271828/p/17552339.html