数据结构与算法概述

Word count: 8.7kReading time: 30 min

 2021/06/15   Share

一、数据结构

1.1 概述

1.1.1 数据结构是什么？

对于数据结构这个概念，至今尚未有一个被一致公认的定义，不同的人在使用这个词时所表达的意思有所不同。

“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。” —— Sartaj Sahni，《数据结构、算法与应用》

“数据结构是ADT（抽象数据类型 Abstract Data Type）的物理实现。” —— Clifford A.Shaffer，《数据结构与算法分析》

“数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。” —— 维基百科

到底什么是数据结构？

数据对象在计算机中的组织方式，包括：
- 逻辑结构
- 物理存储结构：逻辑结构在机器的内存里面怎么放
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

所有的数据都是由数据元素构成，数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成，数据项是数据的不可分割的最小单位。

1.1.2 数据结构存在的目的

让我们操作里面的数据，快速。

方便我们增加
方便我们快速查找到(查是删改的前提)
节省空间(存储)

当然，操作的时候，不光与数据结构有关，与算法的精妙程度也有关系。

今天主要总结一下逻辑结构和存储结构。

1.1.3 抽象数据类型(Abstract Data Type)

描述数据结构有一个很好的方法 - 抽象数据类型

两个关键词：抽象、数据类型

数据类型(包含两部分内容)
- 数据对象集
- 数据集合相关联的操作集

C语言中是单独处理的，在高级语言中，通常会用类将数据集跟和它相关的操作集封装在一起

抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

1.2 什么是逻辑结构？

简单说，逻辑结构就是数据之间的关系。

按数据之间的关系来说，逻辑结构大概可以分为两种:

线性结构
- 线性表：顺序表、链表（线性链表、循环链表、双向链表）
- 栈（顺序栈、链栈）
- 队列（顺序队列、链队列(循环链等)）
- …
非线性结构
- 集合
- 树(二叉树)
- 图(网)
- …

1.2.1 线性结构

有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。它们共同的特点就是数据之间的线性关系，除了头结点和尾结点之外，每个结点都有唯一的前驱和唯一的后继，也就是所谓的一对一的关系。

不同的线性表之间的区别：

线性表在元素的关系上是一样的，都是”线性”关系，不同的线性表区别主要体现在不同的特性上。
比如：队列的先进先出、栈的后进先出等。

以链栈，链队列为例：

逻辑结构同为线性表，存储结构也相同，都是链式存储的，每个结点都是由数据域和指针域组成，每个结点也都有唯一的前驱和唯一的后继（除头尾结点外）。
那么它们看起来就很相似，区别呢？区别就在于给他们定义的特殊操作，它们都有”出”和”入”两种操作，一个是”先进先出”，而一个是”后进先出”。

1.2.2 非线性结构

对应于线性结构，非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。

1.3 什么是存储结构(/物理结构)？

逻辑结构指的是数据间的关系，而存储结构是逻辑结构的存储映像。

常见的存储结构:

顺序存储 – (应用：数组)
链式存储 – (应用：指针)
索引存储
散列存储（哈希表）

1.3.1 顺序存储

把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构。

通常顺序存储结构是借助于数组来描述的。

优点：节省空间，可以实现随机存取；

缺点：插入、删除时需要移动元素，效率低。

1.3.2 链式存储

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

特点是元素逻辑上相邻，但在物理上可以不相邻，所以每个数据元素包括了一个数据域和一个指针域，数据域用来存放数据，而指针域用来指向其后继结点的位置。

优点：

插入、删除灵活 (不必移动节点，只要改变节点中的指针)

缺点：

不能随机存取，查找速度慢。
比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。

1.3.3 索引存储

除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

特点：索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。

1.3.4 散列存储

散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。

特点：散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问。

理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。

1.4 逻辑结构和存储结构的区别

文件的逻辑结构：是用户可见结构，即从用户观点出发观察到的文件组织。
- 用途：为了描述数据之间的联系
文件的物理结构：文件的存储结构，即文件在外存的存储组织形式。涉及存储介质、外存分配方式。
- 用途：关注于如何能使数据的增删改查更简单快捷。

文件组织结构：

通俗点说：用户要看到的数据就是这个结构(字符流式、记录式等)的，而存储介质怎么存(连续、链式、索引)，是连续存，还是拆开了(RAID)，用户是不管的。

二、算法

2.1 什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法：
- 12世纪的算法：是指用阿拉伯数字进行算术运算的过程。
- 数学中的算法：通常是指按照一定规则解决某一类问题的明确和有限的步骤。
  - 一类问题：如判断一个整数是否为质数，求任意一个方程的近似解等，算法可以重复使用。
- 现代算法：通常可以编成计算机程序，让计算机执行并解决问题。

计算机解决任何问题都要依赖于算法，只有将解决问题的过程分解为若干个明确的步骤，即算法，并用计算机能够接受的“语言”准确地描述出来，计算机才能够解决问题．

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。

设计一个具体问题的算法，通常按以下步骤：

认真分析问题，找出解决此题的一般数学方法；
借助有关变量或参数对算法加以表述；
将解决问题的过程划分为若干步骤；
用简练的语言将这个步骤表示出来。

计算机中算法可分为如下两大类：

数值运算算法：求解数值。
非数值运算算法：事务管理领域。

2.1.1 图灵机Turing-machine

英国数学家图灵提出的计算模型, 一个两端无限长的由小格子组成的带子，每个格子可以存储一个数，一个可以在带子左右移动的游标或者指针或者不如叫磁头(head), 磁头可读或修改格子里的数。

默认说的是确定性图灵机，和非确定性图灵机功能上等价。

2.1.2 算法的几个特征

接受一些输入（有些情况下不需要输入）
产生输出 (否则算法就没有意义)
一个有限指令集，即一定在有限步骤之后终止 (跟程序不一样，有些程序可以一直跑，比如说操作系统，不关机的时候一直跑，算法是没有无限循环这个概念的)
每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能处理的范围之内
- 描述应不依赖于任何一种计算机语言以及具体的实现手段(描述要抽象)

2.1.3 总结

算法具有4个性质：输入、输出、有限性、确定性
算法是方法，程序是方法的具体实现

著名计算机科学家沃思提出了下面的公式: 程序 = 数据结构 + 算法;

实际上，一个程序应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，可以用下面的公式表示：程序 = 算法 + 数据结构 + 程序设计方法 + 语言和环境;

2.1.4 常见算法有许多种

算法预览：

简单点的比如：递归、递推、迭代、穷举、概率算法、随机算法等

复杂些的比如：分治算法、贪心算法、动态规划、回溯法、分支限界等，后面会赘述一些这几种算法的基本思想与常见应用。

2.2 影响算法速度的因素

2.2.1 概述

不一样规模的问题，处理起来的难度是不一样的 → 数据的组织方式 → 解决问题方法的效率
空间的利用效率 → 解决问题方法的效率

算法由三部分影响：

存储结构
算法的空间复杂度
算法的时间复杂度

2.2.2 算法时间调试工具

clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。

常数 CLK_TCK (或 CLOCKS_PER_SEC)：机器时钟每秒所走的时钟打点数。

#include <stdio.h> 
#include <time.h>

clock_t start, stop; 
/* clock_t是clock()函数返回的变量类型 */ 
double duration; 
/* 记录被测函数运行时间，以秒为单位 */

int main () 
{ 
    /* 不在测试范围内的准备工作写在clock()调用之前*/ 

    start = clock(); /* 开始计时 */ 
    MyFunction(); /* 把被测函数加在这里 */ 
    stop = clock(); /* 停止计时 */ 
    duration = ((double)(stop - start))/CLK_TCK; 
    /* 计算运行时间 */
    /* 其他不在测试范围的处理写在后面，例如输出duration的值 */ 
    return 0;
}

如果程序运行太快，不足一个时钟打点，那就让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可。

2.3 评判算法优劣的两个标准

2.3.1 空间复杂度、时间复杂度

空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度T(n) —— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

算法时间复杂度：针对指定基本运算，计数算法所做运算次数。

排序：元素之间的比较
检索：被检索元素x与数组元素的比较
整数乘法：每位数字相乘(位乘)1次 m位和n位整数相乘要做mn次位乘
矩阵相乘：每对元素乘1次
- i×j 矩阵与 j×k 矩阵相乘要做 ijk 次乘法
图的遍历：置指针

对于相同输入规模的不同实例，算法的基本运算次数也不一样，可定义两种时间复杂度

最坏情况下的时间复杂度 W(n)
- 算法求解输入规模为 n 的实例所需要的最长时间
平均情况下的时间复杂度 A(n)
- 在给定同样规模为 n 的输入实例的概率分布下，算法求解这些实例所需要的平均时间。计算方式：每一个输入数据对应的输出解的概率 * 对应的基本运算的次数之和

最坏情况复杂度 T_worst(n) > 平均复杂度 T_avg(n)。

之所以要写成n的函数，是因为这两个指标都跟我们要处理的数据的规模直接相关
机器运算做加减法比做乘除法快很多，所以一般都是在数函数做了多少次乘除法，加减法可以忽略不计。

2.3.2 复杂度的渐进表示法

不对算法做非常精细的分析，只粗略地知道它的一个增长趋势就可以了

T(n) = O(f(n)) 表示存在常数 C > 0, n0 > 0 使得当 n > n0 时有 T(n) <= C·f(n)
- 简单来说就是，对充分大的n来说，O(f(n))就表示f(n)是T(n)的某种上界
T(n) = Ω(g(n)) 表示存在常数 C > 0, n0 > 0 使得当 n > n0 时有 T(n) >= C·g(n)
- 对充分大的n来说，g(n)是T(n)的某种下界
T(n) = Θ(h(n)) 表示同时有 T(n) = O(h(n)) 和 T(n) = Ω(h(n))

上界、下界都有无穷个，但是太大的上界、太小的上界对我们分析算法的效率没有帮助，一般我们取最小的上界与最大的下界。

2.3.3 复杂度分析小窍门

若两段算法分别有复杂度T1(n) = O(f1(n)) 和 T2(n) = O(f2(n))，则
- T1(n) + T2(n) = max( O(f1(n)), O(f2(n)) )
- T1(n) × T2(n) = O(f1(n) × f2(n))
若 T(n) 是关于n的k阶多项式，那么 T(n) = Θ(n^k)
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else 结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大

当我们发现这个算法是 O(N^2) 的时候，应该本能的想到有没有可能把它改进为 NlogN (尝试分治策略)

递归的时间复杂度一般稍微有点复杂，耐心一步一步分析带入、化简、计算。

2.3.4 常见的几种复杂度级别

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。 —— 维基百科

常数级复杂度：
- 不管数据有多大，程序处理所花的时间始终是那么多的，我们就说这个程序很好，具有 O(1) 的时间复杂度，也称常数级复杂度；
对数级复杂度：
- 渐进法表示对数级复杂度，底数具体为多少不重要。算法时间复杂度为 log(n) 时，不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。
- 比如：log2(N) / log3(N)，运用换底公式后得：(lnN/ln2) / (lnN/ln3) = ln3/ln2，ln为自然对数，显然这是个常数，与变量N无关。
线性级复杂度：
- 数据规模变得有多大，花的时间也跟着变得有多长，比如找n个数中的最大值这个程序的时间复杂度就是 O(n)，为线性级复杂度。
平方级复杂度：
- 像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，时间复杂度是 O(n^2)，为平方级复杂度。
指数级复杂度：
- 还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 O(a^n) 的指数级复杂度(EXPTIME算法)
甚至还存在 O(n!) 的阶乘级复杂度。

容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。像 O(1)，O(ln(n))，O(n^a) 等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置；

另一种像是 O(a^n) 和 O(n!) 等，它是非多项式级的复杂度，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

对于同一个问题，不同的算法可能会产生不同的复杂度。最典型的例子就是排序，对于n个整数，选择排序和冒泡排序的复杂度为 O(n^2)，快速排序的复杂度为 O(nlogn)，而使用基数排序的复杂度仅为 O(mn)。

三、P、NP、NPC、NP-Hard、P=NP?

3.1 确定性算法

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

3.2 非确定性算法

设A是求解问题B的一个解决算法，它将问题分解成两部分，分别为猜测阶段和验证阶段，其中：

猜测阶段：在这个阶段，对问题的一个特定的输入实例x产生一个任意字符串y，在算法的每一次运行时，y的值可能不同，因此，猜测以一种非确定的形式工作。
验证阶段：在这个阶段，用一个确定性算法（有限时间内）验证。
- ① 检查在猜测阶段产生的y是否是合适的形式，如果不是，则算法停下来并得到no；
- ② 如果y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。它是验证所猜测的解的正确性。

3.3 判定问题Decision question

判定问题是数理逻辑中的一个重要问题。它表现为寻求一种能行的方法、一种机械的程序或者算法，从而能够对某类问题中的任何一个在有穷步骤内确定其是否具有某一特定的性质。

简而言之：答案是yes或者no的问题

3.4 规约/约化

问题A可以约化为问题B，称为“问题A可规约为问题B”，可以理解为问题B的解一定就是问题A的解，因此解决A不会难于解决B。由此可知问题B的时间复杂度一定大于等于问题A。

《算法导论》中有一个例子：现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。

从规约的定义中我们看到，一个问题规约为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断规约，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP-完全问题。

3.5 P问题

Polynomial-time问题，能够在 多项式时间内用算法求解的问题。

P问题意味着计算机能够在有限时间内完成计算。整数排序问题就是P问题，不管你是采用冒泡排序还是快速排序，也无论你是对于10个整数排序还是10亿个整数排序。

3.6 NP问题

Nondeterministic polynomial-time问题，即 非确定性多项式时间，指不确定是否存在多项式时间的求解算法，但可以在多项式时间内验证一个猜测解的正确性的问题。

也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。P类问题属于NP问题，但NP类问题不一定属于P类问题。

1、N皇后问题。在学习数据结构和算法这门课时，有一个比较经典的问题叫做“八皇后问题”，它要求在一个国际象棋的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。这里我们把棋盘扩展到 N*N，并在其中摆放N个皇后，其他要求一样。

这个问题就是一个NP问题，至今为止暂时还没有多项式时间的解法。不过我们很容易验证一个解是否满足要求：对于这N个皇后中的每一个，都检查其所在行，所在列和两个斜线方向是否有其他皇后，即可验证这个解是否是正解，这种验证方法的复杂度为O(n)。

2、划分问题。以下38个整数的和为2000000：

1
2
3

14175,15055,16616,17495,18072,19390,19731,22161,23320,23717,26343,28725,29127,32257,40020,
41867,43155,46298,56734,57176,58306,61848,65825,66042,68634,69189,72936,74287,74537,81942,
82027,82623,82802,82988,90467,97042,97507,99564

要求把它们平均分为两组，每组的19个数字之和都是1000000。

求解这个题其实并不容易，把这38个数分为两组总共有17672631900种方式。也许求出结果对于当今的计算机来说并非遥不可及，程序稍微优化一些其实并不用枚举其中的每一种情况（比如取到前17个数就已经超过1000000时，不用再取第18个和第19个数了）。然而如果是把2000个数分为两组呢？恐怕世界上最好的计算机也无能为力了。

不过，验证这个问题的解却非常容易，只需检验一下在同一组的19个数的和是不是1000000即可。

3.7 NPC问题(NP完全问题)

Non-deterministic Polynomial complete problem ，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。NPC包含了NP中最难的问题。

其定义要满足2个条件：

它是一个NP问题；
所有NP问题都能规约到它。

在1971年，斯蒂芬·库克找到了第一个这样的问题：可满足性问题。简要来说，就是对于N个布尔类型的变量，它们之间采用“与”，“或”，“非”这样的逻辑运算符连接，那么这些变量能否找到一组合适的取值，使得最终的运算结果为真。与之相同的是逻辑电路问题，它其实就是可满足性问题的数字电路实现，用高电平和低电平表示真和假，用与门，或门和非门表示逻辑运算符。

伯克利的教授理查德·卡普在读过库克的论文之后，发现有一种方法可以把可满足性问题归约到团问题。团问题大致是这样一类问题：对于任意两个人，要么是微信好友，要么不是微信好友。那么能否找到一个人数为50个人的团体，使得他们两两之间彼此都是微信好友？因为库克证明了可满足性问题是NP问题中最难的问题，而卡普得到的则是，团问题不比可满足性问题要简单，至少它们一样难。卡普不仅证明了团问题是NP问题中最难的一个，而且他还找到了19个同样难度的重要问题，比如哈密顿回路，旅行商问题，最大割问题等等。1972年，他在他的论文《Reducibility Among Combinatorial Problems》中，提出了这21个NP中最难的问题。

那么这些问题叫什么名字呢？在1973年，曾经做了一次投票调查，在投票中出现了几个候选项——herculean, formidable, arduous, intractable, obstinate等等，不过最终胜出的还是”NP-Complete”（NP完全）。complete表示完全或者完备，一个事实集合被称为是完备的，表明它能解释某些逻辑系统的所有真命题。这也比较符合解决了NP完全问题，就能解决所有其他的NP问题的事实。NP完全问题也简称为NPC问题。

3.8 P=NP?

P=NP? 通常被认为是计算机科学最重要的问题。再回顾一下P、NP的定义：

P是可在多项式时间内用确定算法求解的问题。
NP是可在多项式时间内用不确定算法求解的问题。
- 前面知道，NP包含P，所以“P=NP?”问题的关键，就在于P是否也包含了NP。也就是说，如果使用确定算法，能否在多项式时间之内，解决所有不确定性算法能在多项式时间内解决的问题。

我们再来细看一下什么是多项式时间（Polynomial time）。我们都知道，n^2 是多项式，n^1000000 也是多项式。多项式与多项式之间，却有天壤之别。把解决问题所需要的时间，用“多项式”这么笼统的概念来描述，其实是非常不准确的做法。在实际的大规模应用中，n^2 的算法都嫌慢。能找到“多项式时间”的算法，根本不能说明任何问题。对此，理论家们喜欢说，就算再大的多项式(比如 n^1000000，也不能和再小的指数函数（比如 1.0001^n）相比。因为总是“存在”一个M，当n>M的时候，1.0001^n 会超过 n^1000000。

可是问题的关键，却不在于M的“存在”，而在于它的“大小”。如果你的输入必须达到天文数字才能让指数函数超过多项式的话，那么还不如就用指数复杂度的算法。

所以，“P=NP?” 这问题的错误就在于，它并没有针对我们的实际需要，而是首先假设了我们有“无穷大”的输入，有“无穷多”的时间和耐心，可以让多项式时间的算法“最终”得到优势。

3.9 NP难问题

Non-deterministic Polynomial hard problem(NPH)问题，如果所有NP问题都可归约成某个问题，则该问题称为NP难问题。( 满足NPC问题定义的第二条但不一定要满足第一条)

NPC问题是NP难问题的一个子集。网上看到过一幅表明P问题，NP问题，NPC问题和NP难问题的关系图，觉得非常棒，这里引用过来。

前面说过如果P=NP，那么所有的NP问题都存在有效的解决方案，而对于NP难问题来说，即使P=NP，也不一定存在有效的解决方案。

3.10 求解难问题

对于一个NP问题甚至是NP难问题，通常都无法找到有效的解决方案，于是隔壁老王跟老板说：这个问题我解决不了，并且你找任何人都解决不了。老板想了想之后，把隔壁老王开除掉了，毕竟谁都解决不了，那就干脆不雇佣人好了，还能省点儿钱。

几天之后，有个叫小明的同学跟老板说：你交给隔壁老王的那个问题要求有些太高，现在没有人能解决。但是如果把要求稍微降低些，我能给你提供一个不错的解决方案。于是老板想了想觉得可以接受，于是就雇佣了小明，顶替隔壁老王之前的岗位。

在遇到几乎不可能做到的问题时，我们通常会选择退而求其次，寻找一个还能说得过去的方案。

比如我们要寻找从国贸到中关村的最短距离（当然这个问题使用穷举法也不会算太长时间，仅仅是举个栗子。如果你觉得不过瘾，可以考虑从杭州西湖到中关村的最短距离），由于中间的道路比较繁杂，穷举起来数目非常多，于是我们可以采用一种优化的方案：约定中途需要经过西直门。首先寻找从国贸到西直门的最短距离，然后寻找从西直门到中关村的最短距离。显然从国贸到中关村的最短距离，一定不会比从国贸到西直门的最短距离加上从西直门到中关村的最短距离要长。这么做虽然得到的可能不是最短距离的出行方案，不过却可以缩短我们的搜索范围，大大提高了解决问题的效率。当然，你还可以在国贸和西直门之间锁定另外一个地方，比如南锣鼓巷。很多地图软件就是采用这样的方案提供路线的。

上面提到的机器学习中的特征选择问题，通常采取的做法是使用前向搜索这种启发式算法：每次从所有未选择的特征中选择一个使评价结果最佳的特征，加入到备选子集中，直到加入任何特征时评价结果无法更好，或者达到了限定的特征数。这样做不能保证达到全局最优，不过却使得实现起来变得可能。

参考链接

Author：Tenloy

原文链接：https://tenloy.github.io/2021/06/15/datastruction-overview.html

发表日期：2021.06.15 , 9:40 AM

更新日期：2024.04.07 , 8:02 PM

Next Post

穷举、递推、迭代(辗转法)、递归算法
Previous Post

前端各种模块化方案总结

CATALOG

一、数据结构
二、算法
三、P、NP、NPC、NP-Hard、P=NP?

