算法笔记

1 引言

1.2 非递归算法的基本分析方法

排序算法 sort

1.3 计算时间的渐进表示方法

O,Ω,Θ.

1. O（大O符号，Upper Bound，上界） 定义：若存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有 f(n) ≤ c·g(n)，则 f(n) = O(g(n))。 含义：f(n) 的增长速度不会超过 g(n) 的常数倍，表示算法的最坏情况复杂度。 判断方法：找出常数 c 和 n₀，使得 n ≥ n₀ 时 f(n) ≤ c·g(n) 恒成立。

2. Ω（大欧米伽符号，Lower Bound，下界） 定义：若存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有 f(n) ≥ c·g(n)，则 f(n) = Ω(g(n))。 含义：f(n) 的增长速度不会低于 g(n) 的常数倍，表示算法的最优情况复杂度。 判断方法：找出常数 c 和 n₀，使得 n ≥ n₀ 时 f(n) ≥ c·g(n) 恒成立。

3. Θ（大西塔符号，Tight Bound，紧确界） 定义：若同时存在正常数 c₁、c₂ 和 n₀，使得对所有 n ≥ n₀，有 c₁·g(n) ≤ f(n) ≤ c₂·g(n)，则 f(n) = Θ(g(n))。 含义：f(n) 的增长速度与 g(n) 相同，表示算法的渐进紧确界。 判断方法：找出常数 c₁、c₂ 和 n₀，使得 n ≥ n₀ 时 c₁·g(n) ≤ f(n) ≤ c₂·g(n) 恒成立。

2 分治/规模压缩引入

2.1 分治

• 分
• 治
• 合并

T(n) = aT(n/b) + f(n)

3 算法分析方法

3.2 分析方法

3.2.1 代入法（Substitution Method）

代入法的基本思想是：

1. 猜测递归式的解的渐进上界或下界。
2. 用数学归纳法证明猜测的解是正确的。

例子：

设 $T(n) = 2T(n/2) + n$，猜测 $T(n) = O(n \log n)$。

• 归纳假设：对所有小于 $n$ 的值成立，即 $T(k) \leq c k \log k$。
• 代入递归式： \(T(n) = 2T(n/2) + n \leq 2c\frac{n}{2}\log\frac{n}{2} + n = c n \log\frac{n}{2} + n = c n (\log n - 1) + n = c n \log n - c n + n\)
• 只要 $c$ 充分大，则 $T(n) \leq c n \log n$ 成立。

3.2.2 递归树法（Recursion Tree Method）

递归树法通过画出递归展开的树形结构，计算每一层的代价并求和。

例子：$T(n) = aT(n/b) + n$

• 第 0 层：$n$
• 第 1 层：$a \times (n/b) = (a/b) n$
• 第 2 层：$a^2 \times (n/b^2) = (a/b)^2 n$
• …
• 第 $k$ 层：$a^k \times (n/b^k) = (a/b)^k n$

直到 $n/b^k = 1$，即 $k = \log_b n$

每层的总代价为 $(a/b)^k n$，将所有层相加： \(T(n) = n \sum_{k=0}^{\log_b n} \left(\frac{a}{b}\right)^k = n\frac{1-(a/b)^{\log_b n}}{1-(a/b)}\)

• 若 $a < b$，则为等比数列收敛，$T(n) = O(n)$
• 若 $a = b$，则每层代价为 $n$，共 $\log_b n$ 层，$T(n) = O(n \log n)$
• 若 $a > b$，则为等比数列发散，$T(n) = O(n^{\log_b a})$

这就是递归树法对 $T(n) = aT(n/b) + n$ 的复杂度分析。

3.2.3 主定理

对于分治递归式：

常用的求解方法是主定理（Master Theorem）：

• 若 $f(n) = O(n^{\log_b a - \epsilon})$，则 $T(n) = \Theta(n^{\log_b a})$
• 若 $f(n) = \Theta(n^{\log_b a}\log^k n)$，则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$
• 若 $f(n) = \Omega(n^{\log_b a + \epsilon})$，且 $a f(n/b) \leq c f(n)$，则 $T(n) = \Theta(f(n))$

其中 $a \geq 1, b > 1, \epsilon > 0, c < 1，k \geq 0$。

常见例子：

• 归并排序：$T(n) = 2T(n/2) + O(n)$

  计算过程： $a=2,\ b=2,\ f(n)=O(n)$ $\log_b a = \log_2 2 = 1$ $f(n) = O(n^{1})$ 属于主定理第二种情况： $T(n) = \Theta(n \log n)$

• 二分查找：$T(n) = 2T(n/2) + O(1)$

  计算过程： $a=2,\ b=2,\ f(n)=O(1)$ $\log_b a = \log_2 2 = 1$ $f(n) = O(n^1)$ 属于主定理第二种情况： $T(n) = \Theta(n)$

• $T(n) = 2T(n/2) + n^2$

  计算过程： $a=2,\ b=2,\ f(n)=n^2$ $\log_b a = 1$ $f(n) = \Omega(n^{1+\epsilon})$，且 $a f(n/b) = 2 (n/2)^2 = n^2/2 \leq 0.5 n^2$ 属于主定理第三种情况： $T(n) = \Theta(n^2)$

• $T(n) = 4T(n/2) + n$

  计算过程： $a=4,\ b=2,\ f(n)=n$ $\log_b a = \log_2 4 = 2$ $f(n) = O(n^{2-\epsilon})$ 属于主定理第一种情况： $T(n) = \Theta(n^2)$

3.3

各种排序算法的比较

10 相关思想

1. 分治算法（Divide and Conquer）

核心思想：将问题分解为若干子问题，递归求解子问题，再合并子问题的解得到原问题的解。
适用条件：问题可分解为相互独立的子问题，且子问题的解能合并为原问题的解。

一般步骤：

1. 分（Divide）：
   • 将原问题分解为若干个规模较小的相似子问题。
   • 例如：归并排序中将数组分成左右两半。
2. 治（Conquer）：
   • 递归求解子问题。若子问题规模足够小，则直接求解。
   • 例如：排序单个元素的数组。
3. 合并（Combine）：
   • 将子问题的解合并为原问题的解。
   • 例如：归并排序中合并两个已排序的子数组。

经典例子：

• 归并排序、快速排序、二分查找、汉诺塔问题。

2. 动态规划（Dynamic Programming, DP）

核心思想：通过将问题分解为重叠子问题，并存储子问题的解（避免重复计算），从而高效求解原问题。
适用条件：问题具有最优子结构和重叠子问题性质。

一般步骤：
动态规划的一般方法

1. 刻画最优解的结构（最优子结构）
   • 对应规模压缩的：分、治、合并
2. 递归定义最优解的值（最好有多好）
   • 常需列举所有子问题情况
3. 自下而上完成计算
   • 如需最优解，记住挑了谁
4. 构造最优解
   • 递归完成

经典例子：

• 编辑距离、背包问题、最长公共子序列（LCS）、斐波那契数列。

3. 贪心算法（Greedy Algorithm）

核心思想：每一步选择当前局部最优解，希望最终得到全局最优解。
适用条件：问题具有贪心选择性质（局部最优能导致全局最优）。

一般步骤：

通过局部最优选择尝试达到全局最优解

1. 问题分解：
   • 将问题分解为多个步骤或阶段。
2. 贪心选择：
   • 在每个步骤中，选择当前最优的决策（不回溯）。
   • 例如：霍夫曼编码中每次合并频率最小的两个节点。
3. 更新问题状态：
   • 根据选择更新问题的剩余部分。
4. 迭代直至解决：
   • 重复步骤2-3，直到问题解决。

经典例子：

• 霍夫曼编码、Dijkstra算法（最短路径）、活动选择问题、最小生成树（Prim/Kruskal）。

4. 回溯算法（Backtracking）

回溯算法是一种通过递归试探和撤销选择来搜索所有可能解的算法。它通常用于解决组合问题、排列问题、子集问题等需要遍历所有可能情况的问题。

核心思想

1. 试探性选择：在每一步尝试一个可能的选项，并进入下一层决策。
2. 约束条件：如果当前选择不满足问题的约束条件，则回溯（撤销选择）。
3. 目标状态：当找到一个可行解时，记录或输出；如果需要所有解，则继续搜索。

一般步骤

1. 定义解空间
   • 确定问题的解形式（如排列、子集、棋盘布局等）。
   • 例如：全排列问题的解是 [a, b, c] 的所有排列方式。
2. 选择与递归
   • 在每一步，选择一个候选值加入当前解，并递归进入下一层决策。
   • 例如：在排列问题中，选择一个未被使用的数字加入当前排列。
3. 约束条件检查（剪枝）
   • 如果当前选择违反约束条件（如重复使用元素、超出限制等），则跳过该选择。
   • 例如：在 N 皇后问题中，如果当前位置会攻击已放置的皇后，则回溯。
4. 回溯（撤销选择）
   • 在递归返回后，撤销上一步的选择，尝试其他可能性。
   • 例如：在全排列问题中，将当前数字从排列中移除，尝试其他数字。
5. 终止条件
   • 当找到一个可行解或遍历完所有可能时停止递归。
   • 例如：当排列长度等于输入数组长度时，记录该排列。

经典例子

1. 全排列问题（Permutations）
   • 解空间：[1, 2, 3] 的所有排列（如 [1,2,3], [1,3,2], …）。
   • 约束条件：每个数字只能使用一次。
   • 回溯过程：选择 1 → 选择 2 → 选择 3（得到一个排列），然后回溯尝试 2 → 3 → 1 等。
2. N 皇后问题
   • 解空间：在 N×N 棋盘上放置 N 个皇后，使其互不攻击。
   • 约束条件：皇后不能在同一行、列或对角线。
   • 回溯过程：尝试在第一行放置皇后，递归进入下一行，如果冲突则回溯。
3. 子集问题（Subsets）
   • 解空间：数组的所有可能子集（如 [1, 2] 的子集是 [], [1], [2], [1,2]）。
   • 回溯过程：选择是否将当前数字加入子集，递归进入下一层。

与分治、DP、贪心的对比

总结

• 回溯适用于需要穷举所有可能解的问题，通过递归和剪枝优化搜索效率。
• 分治和 DP 更适合优化问题（如最短路径、最大值），而 贪心 适用于局部最优能导向全局最优的问题。
• 关键区别：回溯会撤销选择（试错），贪心和DP一旦做出选择则不回溯。

11 相关题目

排序

大/小顶堆

大顶堆插入调整（上浮）：

1. 将新元素插入到堆的末尾。
2. 设当前插入元素的下标为 i。
3. 当 i > 0 且堆中当前元素大于其父节点时，交换当前元素与父节点。
4. 将 i 更新为父节点下标，重复第 3 步，直到堆性质满足或到达根节点。

优先级队列

优先级队列（Priority Queue）是一种特殊的队列数据结构，它每次从队列中取出的元素总是优先级最高的元素（而不是最先进入队列的元素）。优先级通常可以是数值（数值越大或越小表示优先级越高），也可以是某种比较规则。

常见的实现方式有：

使用 堆（Heap），如最小堆或最大堆，时间复杂度为 O(log n)。

使用排序数组或链表（插入时排序），适合元素不频繁变动的场景。

快速排序

快速排序（Quicksort）是一种分治法（Divide and Conquer）思想的排序算法，平均时间复杂度为 O(n log n)，最坏情况为 O(n²)，但在实际中表现非常优秀，是常用的排序算法之一。

🔧 原理简述：

1. 从数组中选择一个元素作为“基准值”（pivot）；

2. 将小于基准值的元素放到左边，大于的放到右边（称为分区（partition））；

3. 对左右两个子数组递归进行快速排序；

排序完成。

第i小元素

DP

矩阵链乘

矩阵链乘（Matrix Chain Multiplication）问题是动态规划的经典问题，其目标是在给定的一系列矩阵中，找到一种最优的加括号方式（乘法顺序），以使标量乘法次数最少。

问题描述

给定一系列矩阵 $A_1, A_2, …, A_n$，其中矩阵 $A_i$ 的维度为 $p_{i-1} \times p_i$，要计算 $A_1A_2…A_n$ 的乘积。 由于矩阵乘法满足结合律，但不满足交换律，不同的括号化顺序会导致不同的计算代价（即乘法次数不同）。

递推公式

含义解释：

• $m[i][j]$：表示从矩阵 $A_i$ 到 $A_j$ 连乘的最小计算代价（乘法次数）
• $p$：维度数组，矩阵 $A_i$ 的维度为 $p_{i-1} \times p_i$
• 递推通过尝试所有划分点 $k \in [i, j-1]$，找出最优切分点

最大子数组和

最大子数组和（Maximum Subarray Sum）问题是动态规划中的经典问题，其目标是在一个数组中找到和最大的连续子数组，并返回其和。

类似于矩阵连乘问题的区间动态规划思想，可以将区间 $[i, j]$ 的最大子数组和划分为三类：

1. 完全在 $[i, k-1]$ 区间内的最大子数组和
2. 完全在 $[k+1, j]$ 区间内的最大子数组和
3. 包含 $k$ 的最大子数组和（即跨越 $k$ 的子数组）

递推公式： \(maxSum(i, j) = \max\left\{ maxSum(i, k-1), maxSum(k+1, j), maxCrossingSum(i, j, k) \right\}\) 其中 $maxCrossingSum(i, j, k)$ 表示跨越 $k$ 的最大子数组和，可以通过从 $k$ 向左、向右分别累加最大和得到。

分治法实现思路：

1. 递归求解左半部分 $[i, k-1]$ 的最大子数组和。
2. 递归求解右半部分 $[k+1, j]$ 的最大子数组和。
3. 计算包含 $k$ 的最大子数组和。
4. 取三者最大值。

该方法的时间复杂度为 $O(n \log n)$。

当然，最大子数组和问题也可以用线性动态规划（Kadane算法）$O(n)$ 求解。

装配线问题

问题描述

一家公司有两条装配线（Line 1 和 Line 2），每条线有 n 个工位（station），每个工位只能由该线的某个工人操作，每个工位的加工时间不同。

• 从一个工位到下一个工位有两种选择：

  • 留在同一条线上，继续到下一个工位；
  • 转移到另一条线（有一个固定的转移代价）。

• 开始与结束时还要考虑进入线和离开线的时间。

输入：

• a[2][n]：在每条线第 j 个工位的加工时间（a[0][j] 表示线1第j站时间）。
• t[2][n-1]：从一条线第 j 个站转移到另一条线第 j+1 个站所需的时间。
• e[2]：进入每条线所需时间。
• x[2]：离开每条线所需时间。

目标：

找出从工位1到工位n所需的最小总时间路径，可以在每个工位选择继续或切换装配线。

递推公式

• f1[j] 表示到达线1第 j 个站的最小时间
• f2[j] 表示到达线2第 j 个站的最小时间

则状态转移如下（从第1个工位到第n个工位）：

最终最优时间为：

示意图（可选）

Line 1: e1 → a1[1] → a1[2] → ... → a1[n] → x1
                      ↘↑   ↘↑          ↘↑
Line 2: e2 → a2[1] → a2[2] → ... → a2[n] → x2

0-1背包

问题描述

给定 n 个物品，每个物品有重量 w[i] 和价值 v[i]，以及一个最大承重为 W 的背包，每个物品只能选一次，要么选，要么不选。目标是使装入背包的物品的总价值最大。

解法思想：动态规划（DP）

状态定义：

• dp[i][j] 表示前 i 个物品，在容量为 j 的背包下的最大价值。

状态转移：

if (j < w[i])  
    dp[i][j] = dp[i-1][j]
else
    dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

最长公共子序列

问题描述

给定两个字符串 X 和 Y，找出它们的最长公共子序列（不要求连续，但顺序不能乱）。

解法思想：动态规划

状态定义：

• dp[i][j] 表示 X[1..i] 与 Y[1..j] 的最长公共子序列长度。

状态转移：

if (X[i] == Y[j])
    dp[i][j] = dp[i-1][j-1] + 1
else
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

贪心

分数背包

问题描述

和 0-1 背包类似，但每个物品可以取部分（即切割），目标是总价值最大。

解法思想：贪心算法（Greedy）

算法流程：

1. 计算每个物品的单位价值：value/weight；
2. 按单位价值从高到低排序；

3. 从高到低依次取物品：

   • 如果物品能全部放入背包，就全部取；
   • 否则按比例取一部分。

时间复杂度：

• O(n log n) （因为需要排序）

活动选择

问题描述

给定若干个活动，每个活动有开始时间 s[i] 和结束时间 f[i]，选择最多不重叠的活动集合。

解法思想：贪心算法

算法流程：

1. 按活动的结束时间从小到大排序；
2. 选取第一个活动；

3. 遍历后续活动：

   • 若当前活动的开始时间 ≥ 上一个选择活动的结束时间，则选择；
   • 否则跳过。

最多活动数即为最优解。

单源最短路径

一、Dijkstra 算法（狄杰斯特拉）

1. 解决问题：

• 用于单源最短路径问题。
• 要求图中边权非负（即不能存在负权边）。
• 支持有向图或无向图。

2. 基本思想（贪心策略）：

Dijkstra 使用贪心思想：每次选择“当前未确定最短路径的、距离源点最近的点”，然后更新其邻接点的最短路径估计。

3. 算法步骤：

1. 初始化：

   • 距离数组 dist[]：初始为 ∞，源点 dist[src] = 0。
   • 访问数组 visited[]：标记每个点是否确定了最短路径。

2. 重复以下过程 V-1 次：

   • 在 dist[] 中选出一个未访问且距离最小的点 u。
   • 将 u 标记为访问（最短路径确定）。
   • 遍历所有 u 的邻接点 v，如果从 u 到 v 的距离 dist[u] + w(u,v) 小于 dist[v]，则更新它。

3. 所有节点最短路径更新完毕，dist[] 即为结果。

4. 时间复杂度：

• 朴素实现（邻接矩阵）：O(V²)
• 使用堆优化（邻接表 + 最小堆）：O((V + E) log V)

5. 不足之处：

• 无法处理负权边，一旦遇到可能出现错误结果。

Bellman-Ford 算法

1. 解决问题：

• 同样用于单源最短路径问题。
• 可以处理图中存在负权边的情况。
• 可用于检测负权环（环的权值和为负数）。

2. 基本思想（松弛迭代）：

通过反复对所有边进行松弛操作，逐步逼近最短路径。最终收敛到正确结果（若无负环）。

3. 算法步骤：

1. 初始化：

   • 距离数组 dist[]：初始为 ∞，源点 dist[src] = 0。

2. 进行 V-1 次松弛操作：

   • 每一轮遍历所有边 u → v，如果 dist[u] + w(u,v) < dist[v]，就更新 dist[v]。

3. 负环检测（可选）：

   • 再遍历一次所有边，如果还能松弛，说明存在负环。

4. 时间复杂度：

• 普通实现：O(V × E)

5. 特点总结：

输入图结构：

图中有 5 个顶点，边为：

0 → 1 (权重 6)
0 → 3 (权重 7)
1 → 2 (权重 5)
1 → 4 (权重 -4)
2 → 1 (权重 -2)
3 → 2 (权重 -3)
4 → 2 (权重 7)

• Dijkstra 无法处理 -4、-2、-3 这些负边。
• Bellman-Ford 可以正确求出所有点到源点的最短路径。

可视化帮助理解（Bellman-Ford）：

第 i 次松弛后，每个节点的 dist[] 可能如下演变：

如果你需要这两个算法的图形化演示、动态演练、或者与 Floyd / SPFA 等算法做性能或结构对比，也可以继续告诉我！

任意最短路径 DP

Floyd-Warshall 算法 是一种经典的 动态规划算法，用于解决：在加权图中求任意两点之间的最短路径（All-Pairs Shortest Path 问题）

适用图类型：

• 有向或无向图
• 带权（可正可负，但不能有负权环）

输入：

• 顶点数：n
• 邻接矩阵 dist[i][j]：表示从点 i 到点 j 的边权，若无边则为 ∞（用大数表示）

输出：

• dist[i][j]：表示从 i 到 j 的最短路径长度
• 可选地输出路径：使用中间节点矩阵 path[i][j] 记录路径构造信息

核心思想（动态规划）：

设 dist[i][j] 表示从 i 到 j 的最短路径。

状态转移方程（k 为中间节点）：

意思是：如果经过中间点 k，从 i 到 j 的路径会更短，就更新。

算法流程：

1. 初始化：输入邻接矩阵 dist[i][j]
2. 三重循环更新：

for (int k = 0; k < n; k++)       // 中间点
  for (int i = 0; i < n; i++)     // 起点
    for (int j = 0; j < n; j++)   // 终点
      if (dist[i][k] + dist[k][j] < dist[i][j])
        dist[i][j] = dist[i][k] + dist[k][j];

时间复杂度： O(n³)，适合中小规模图（n < 500）

示意图说明：

设图中有三个点：A、B、C 若 A→C 比 A→B→C 更长 那么 Floyd-Warshall 会发现 B 是一个中继点，使路径更短，于是更新 dist[A][C] = dist[A][B] + dist[B][C] 示例（邻接矩阵）：

图：

   A ——1——→ B
   ↓       ↘
   4        2
   ↓         ↘
   C <——3——— B

邻接矩阵 dist 初始化为（不可达设为 ∞）：

运行 Floyd-Warshall 后：

用一个二维数组 path[i][j] 记录每次中转的最短路径中间点，然后通过递归或栈方式构造最短路径。

回溯算法

回溯算法（Backtracking） 是一种通用的搜索策略，用于在所有可能解的空间中系统地搜索解。它可以理解为带剪枝的“暴力搜索”，适用于 组合、排列、子集、图的路径等问题。 回溯算法解决的问题类型

1. 组合类问题
   • 例子：从 $n$ 个数中选出 $k$ 个不重复数
   • 典型题目：组合、组合总和、N 皇后
2. 排列类问题
   • 例子：全排列、字母重新排序
   • 典型题目：全排列、字母排列、数独
3. 子集类问题
   • 例子：某集合的所有子集
   • 典型题目：子集、子集和

4. 路径类问题（图、迷宫）

   • 例子：迷宫寻路、图的 Hamilton 路径、单词搜索
   • 典型题目：单词搜索、解数独、八皇后、迷宫问题

5. 约束满足问题

   • 例子：数独、填字游戏、N 皇后问题
   • 要求满足某些特定规则的安排

回溯算法思想

回溯算法的核心是：

• 尝试每一种可能
• 如果当前路径不合法就“回退”（剪枝）

模板框架（伪代码）：

def backtrack(path, choices):
    if 满足结束条件:
        记录结果
        return
    for choice in choices:
        if 剪枝条件: continue
        做选择
        backtrack(路径 + choice, 剩余选择)
        撤销选择

典型题：N 皇后问题

在 $n \times n$ 的棋盘上放置 n 个皇后，要求任意两个皇后不同行、不同列、不在一条斜线上。

回溯框架是：

• 每行放一个皇后
• 尝试所有列，判断是否冲突
• 不冲突则递归下一行

回溯 vs 动态规划 vs 贪心

常见题目（可配合练习）

NP完全问题

一、P 类问题（Polynomial Time Problems）

定义：

P 类问题指的是所有可以在“多项式时间”内求解的问题。

换句话说：如果一个问题存在一个确定性的算法，该算法的运行时间是输入规模 $n$ 的多项式（如 $O(n^2), O(n^3)$，而不是指数级 $O(2^n)$），则该问题属于 P 类。

举例：

特点：

• 可以快速解出答案
• 确定性算法（不会依赖猜测、非确定行为）
• 适合在实际中高效求解

二、NP 类问题（Nondeterministic Polynomial Time）

定义：

NP 类问题指的是：给出一个候选解，可以在“多项式时间”内验证这个解是否正确。

即：我们不一定能很快找到解，但如果给你一个解，我们能在合理时间内验证它是否对。

通俗理解：

• P 问题：你会很快算出结果
• NP 问题：你不一定会算，但别人给你一个结果，你能很快检查出这个结果对不对

举例：

三、NP-完全问题（NP-complete Problems）

定义：

NP-完全问题是一类最难的 NP 问题，它们具有两个特性：

1. 属于 NP 类（即：给你一个解，能在多项式时间内验证）
2. 所有其他 NP 问题都可以在多项式时间内归约到它（也就是说它是 NP 中最“通用”的）

直白讲：它既是 NP 问题，又是 NP 中最难的那一类。

举例：

四、P vs NP 问题（计算机科学最重要的未解问题）

核心问题：

如果所有能快速验证的问题（NP），也都能被快速解决（P），那就说明 P = NP。

• 如果 P = NP，意味着很多目前只能“暴力试验”的问题将能快速求解——对密码学、安全等领域将造成巨大冲击；
• 如果 P ≠ NP，说明 NP 中很多问题是天生“难解”的。

总结表格

各问题时间复杂度

注：部分问题有多种算法实现，表中取常见最优复杂度。NP完全问题为指数级或更高，实际复杂度依具体问题和实现。

12 中英文对照表