1、算法导论时间复杂度、确定性和非确定性图灵机、算法的确定性与非确定性、P问题、NP问题、规约/约化、NPC问题、NPhard问题

要想了解算法的问题&＃xff0c;首先要知道问题的分类&＃xff0c;而要想知道问题的分类&＃xff0c;就要先了解时间复杂度。

时间复杂度并不是表示一个程序解决问题需要花多少时间&＃xff0c;而是当问题规模扩大后&＃xff0c;程序需要的时间长度增长得有多快。

下面理解一下时间复杂度

不管数据有多大&＃xff0c;程序处理花的时间始终是那么多的&＃xff0c;这个程序则具有O(1)的时间复杂度&＃xff0c;也称常数级复杂度。

数据规模变得有多大&＃xff0c;花的时间也跟着变得有多长&＃xff0c;这个程序的时间复杂度就是O(n)

再来了解一下多项式&＃xff1a;
多项式&＃xff08;polynomial&＃xff09;是指由变量、系数以及它们之间的加、减、乘、幂运算&＃xff08;非负整数次方&＃xff09;得到的表达式&＃xff0c;如下


前五个都是多项式级别的时间复杂度

而非多项式级别的时间复杂度是&＃xff1a; O(a^n), O(n!)&＃xff0c;非多项式级的时间复杂度是计算机不能承受的。

图灵机是由艾伦·麦席森·图灵在1936年描述的一种抽象机器&＃xff0c;它是人们使用纸笔进行数学运算的过程的抽象&＃xff0c;它肯定了计算机实现的可能性&＃xff0c;并给出了计算机应有的主要架构&＃xff0c;引入了读写与算法与程序语言的概念为现代计算机的发明打下了基础。

图灵机中有两类&＃xff1a;确定图灵机和非确定图灵机

在确定性图灵机&＃xff08;DTM&＃xff09;中&＃xff0c;其控制规则规定了在任何给定情况下最多只能执行一个动作。

非确定性图灵机&＃xff08;NTM&＃xff09;是一种理论计算模型&＃xff0c;其控制规则在某些给定情况下指定了多个可能的动作。 也就是说&＃xff0c;NTM的下一个状态不是完全由其动作和它所看到的当前符号决定的&＃xff08;不同于确定性图灵机&＃xff09;。

参考

确定性算法&＃xff1a;设A是求解问题B的一个解决算法&＃xff0c;在算法的整个执行过程中&＃xff0c;每一步都能得到一个确定的解&＃xff0c;这样的算法就是确定性算法。

非确定性算法&＃xff1a;设A是求解问题B的一个解决算法&＃xff0c;它将问题分解成两部分&＃xff0c;分别为猜测阶段和验证阶段

猜测阶段&＃xff1a;在这个阶段&＃xff0c;对问题的一个特定的输入实例x产生一个任意字符串y&＃xff0c;在算法的每一次运行时&＃xff0c;y的值可能不同&＃xff0c;因此&＃xff0c;猜测以一种非确定的形式工作。

验证阶段&＃xff1a;在这个阶段&＃xff0c;用一个确定性算法&＃xff08;有限时间内&＃xff09;验证。

①检查在猜测阶段产生的y是否是合适的形式&＃xff0c;如果不是&＃xff0c;则算法停下来并得到no&＃xff1b;
②如果y是合适的形式&＃xff0c;则验证它是否是问题的解&＃xff0c;如果是&＃xff0c;则算法停下来并得到yes&＃xff0c;否则算法停下来并得到no。它是验证所猜测的解的正确性。

P Problem&＃xff0c;即Polynomial Problem&＃xff0c;即多项式回归问题。

对于任意的输入规模n&＃xff0c;问题都可以在n的多项式时间内得到解决

P问题是具有多项式算法的判定问题。
P问题就是可以有一个确定型图灵机在多项式时间内解决的问题。
即那些存在O&＃xff08;n&＃xff09;&＃xff0c; O&＃xff08;nk&＃xff09;&＃xff0c; O&＃xff08;nlogn&＃xff09;等多项式时间复杂度解法的问题。
比如排序问题、最小生成树、单源最短路径。
直观的讲&＃xff0c;P问题视为可以较快解决的问题。

P &＃61; “确定性计算机”能够在“多项式时间”解决的所有问题

划重点&＃xff1a;多项式时间复杂度&＃xff0c;容易被解决的问题

NP Problem&＃xff0c;即Non-deterministic Polynomial Problem&＃xff0c;即非确定性多项式回归问题

可以在多项式的时间里验证一个解的问题

NP问题是在多项式时间内“可验证”的问题。
也就是说&＃xff0c;不能判定这个问题到底有没有解&＃xff0c;而是猜出一个解来在多项式时间内证明这个解是否正确。
即该问题的猜测过程是不确定的&＃xff0c;而对其某一个解的验证则能够在多项式时间内完成。

NP &＃61; “非确定性计算机”能够在“多项式时间”解决的所有问题

划重点&＃xff1a;多项式时间复杂度&＃xff0c;不知道到底能不能解决的问题

P类问题属于NP问题&＃xff0c;但NP类问题不一定属于P类问题。

问题A可以约化为问题B&＃xff0c;称为问题A可规约为问题B

即&＃xff0c;问题B的解一定就是问题A的解&＃xff0c;因此解决A不会难于解决B

即&＃xff0c;可以用问题B的解法解决问题A

即&＃xff0c;问题A是B的一种特殊情况

由此可知问题B的时间复杂度一定大于等于问题A。

归约
约化性

NPC Problem&＃xff0c;即Non-deterministic Polynomial Complete Problem&＃xff0c;即非确定性多项式回归完全问题

满足两个条件
(1)是一个NP问题
(2)所有的NP问题都可以约化到它

一个NP问题&＃xff0c;使得所有的该类NP问题都可以多项式时间地规约(Polynomial-time Reducibility) 为NPC问题。根据规约的传递性&＃xff0c;对NP问题进行一层接一层地规约&＃xff0c;最终可以得到一个足够泛化的NP问题&＃xff0c;即NPC问题。

所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题&＃xff0c;即解决了此NPC问题&＃xff0c;所有NP问题也都得到解决。

既然所有的NP问题都能约化成NPC问题&＃xff0c;那么只要任意一个NPC问题找到了一个多项式的算法&＃xff0c;那么所有的NP问题都能用这个算法解决了&＃xff0c;NP也就等于P了。

NP hard Problem&＃xff0c;即Non-deterministic Polynomial hard Problem&＃xff0c;即非确定性多项式回归难问题

NP-Hard问题满足NPC问题定义的第二条但不一定要满足第一条
NP-Hard问题要比 NPC问题的范围广&＃xff0c;NP-Hard问题没有限定属于NP&＃xff0c;即所有的NP问题都能约化到它&＃xff0c;但是他不一定是一个NP问题
即使NPC问题发现了多项式级的算法&＃xff0c;NP-Hard问题有可能仍然无法得到多项式级的算法
事实上&＃xff0c;由于NP-Hard放宽了限定条件&＃xff0c;它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决

P问题属于NP问题&＃xff0c;NPC问题属于NP问题。

NPC问题同时属于NP hard问题&＃xff0c;是NP与NPhard的交集。