时间复杂度与问题分类(P、NP、NPC、NP-hard)
参考
- https://blog.csdn.net/sinat_41348401/article/details/122347609
- https://blog.csdn.net/qq_38250032/article/details/81586329
时间复杂度（Time complexity）
定义
时间复杂度：指的是随着问题规模的扩大，解决所需的时间的增长速度，能用来评估执行程序所需的时间。
换言之，即为求解算法的运算量。
多项式时间（Polynomial time）
什么是多项式时间？回答这个问题得先知道计算中常用的时间复杂度排序。
在时间复杂度的计算中常用的时间复杂度按照耗费的时间从小到大依次是：$O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)$.
而多项式时间则包含以上n作为底数的时间复杂度所花时间, 即：$O(1)$到$O(n^{m})$所花时间.
再后面的$O(2ⁿ)、O(n!)$则是指数级问题，也就是我们经常说的爆炸性增长，属于非多项式级复杂度。
区分出多项式时间复杂度与$O(2ⁿ)，O(n!)$型非多项式级复杂度的根本标准是：问题规模较大时，计算机很难算出后者结果。
所以我们需要多项式级复杂度的算法。
问题分类
P(Polynomial)
Polynomial adj.多项式的
我们称一类问题是P，则指在多项式时间可以“解决”的一类问题。
也就是好解决，而且我们解决的还不错，又快又准。
NP（Non-deterministic Polynomial）
Non-deterministic Polynomial 非确定性多项式的
我们称一类问题是NP，则意味着我们能在多项式时间“验证”某个解是否正确。
而与P相比，P类问题（可以解决）必然是NP（可以验证）
但反过来，NP问题是否一定是P问题，则尚未有人证明，是不确定的
（因为若你觉得某NP问题是只能验证不能求解的，别人则可以合理怀疑只是我们还没发现解决的算法）
归约（Polynomial-time Reducibility）
如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可归约为问题B。
在交代什么是NPC之前，得先清楚什么是归约。
简单地说，问题A可以归约为问题B的意思是说：可用问题B的解法解决问题A，或者说，问题A可以“变成”问题B.
例如求解一个一元一次方程和求解一个一元二次方程，我们说，前者可以归约为后者。
是因为知道怎样解一个一元二次方程，那么一定能解出一元一次方程
（因为一元一次方程是一个二次项系数为零的特殊的一元二次方程）
从上面这个例子，我们其实就可以发现：从特殊的小众的问题归约到大问题后，解决的方法变复杂了，时间复杂度增加，但普适性更强，可以在适用在更多范围。
而且归约有一项重要的性质：传递性，A->B->C, 则：A->C
若我们能将一个NP问题不断归约，它就会被归约成一个时间复杂度最高且能「通吃」所有其他NP问题的超级问题，我们管它叫NPC问题。
NPC（NP complete，NP完备）
判断是否为NP完备，有两个依据：
- 这个问题得是NP
- 必须所有NP都可以规约到它
换言之，正如前文所讨论的NP归约，若存在这样一个NP问题，所有的NP问题都可以归约成它，并且这种问题不只一个，它有很多个，是一类问题，就叫为 NP完备 或 NP完全问题。
NP-hard（NP困难）
判断是否为NP困难，同样也是两个依据：
- 必须所有NP都可以规约到它
- 但是它本身并不一定是NP
因为不需要是NP问题，NP-Hard问题要比 NPC问题的范围广。
若有一天，我们找到了NPC问题的多项式时间算法，那么能被归约为这类NPC问题的NP问题都将得到解决。
但是，NP-hard问题仍然无法用多项式算法解决，因为它不是NP问题，连答案的验证都很困难。
🚬
注解：P一定是NP，NP不一定是P（当P!=NP时，见左图；当P=NP时，见右图）。一部分NP可以规约为NPC，一部分NP是NP-hard。NPC和NP-hard有交集。交集的部分就是NP。
？？？不应该是NP和NP-hard有交集。交集的部分就是NPC。
范数（norm）
参考
- https://en.wikipedia.org/wiki/Norm_(mathematics)
- https://blog.csdn.net/weixin_38937984/article/details/102975811
- https://blog.csdn.net/kingzone_2008/article/details/15073987
- 计算方法
定义
范数，是具有“长度”概念的函数。
相关的数学领域，范数是能衡量向量或矩阵的长度的函数。
而衡量的方法很多，对应的「范数」也就不同。
那什么函数能被称为范数，或者说，范数的条件是什么？
一个函数是范数的充要条件：
函数$||x||$
满足非负性$||x|| >= 0$
满足齐次性$||cx|| = |c| •||x|| $
c是常数
满足三角不等式$||x+y|| <= ||x|| + ||y||$
类比三角形任意两边之和大于第三边
分类
向量的范数
L1范数
L1范数是指向量中各个元素绝对值之和。
$$
||x||_1 = \sum^{n} _ {i=1} |x_i|
$$
L2范数(欧几里得Euclidean范数或Frobenius范数)
欧几里得范数（L2范数）为向量各个元素平方和的$\frac{1}{2}$次方。
$$
||x|| = ||x||_2 = \sqrt{\sum\limits^{n} _ {i=1} {x_i}^2}
$$
值得一提，欧几里得范数（Euclidean norm） 也叫 欧式长度(距离) 、 L2 范数 、 L2距离
LP范数
通过以上，相信你已经看出规律了，即：
Lp范数为向量各个元素绝对值p次方和的$\frac{1}{p}$次方。
$$
||x||_p = \sqrt[p]{\sum\limits^{n} _ {i=1} {x_i}^p}
$$
L∞范数
特殊的，我们定义L∞范数为向量各个元素绝对值最大那个元素的绝对值
$$
||x|| _ ∞ = \mathop{max}\limits _ {1≤i≤n}|x _ i|
$$
矩阵的范数
设$x \in R^n, A \in R^{n×n}$
矩阵的列范数
$||x|| _ 1 = \sum\limits^n _ {i=1}{|x_i|}$ 对应 $||A|| _ 1 = \mathop{max}\limits _ {1≤j≤n}\sum\limits^n _ {i=1}{|a_{ij}|}$
矩阵的列范数$||A||_1$即每列元素绝对值之和最大值。
矩阵的行范数
$||x|| _ ∞ = \mathop{max}\limits _ {1≤i≤n}|x _ i|$ 对应 $||A|| _ ∞ = \mathop{max}\limits _ {1≤i≤n}\sum\limits^{n} _ {j=1}|a _ {ij}|$
矩阵的行范数$||A||_∞$即每行元素绝对值之和最大值。