Q&A#

算法的定义
算法的基本特性（5个）
算法与程序的区别？
伪代码怎么写？格式约定？
算法设计的过程，以及贪心算法初步理解
算法复杂度分析包含（2个）？影响时间复杂性的因素？（3个）
渐进符号的含义（4个）
说出具体含义-算法的性质：稳定性、最优性、随机性、在线/离线、近似比
计算复杂性理论（4个问题）
五大经典算法设计策略:贪心算法、动态规划、分治法、回溯法、分支限界法

算法的定义#

算法（Algorithm） 是对特定问题求解步骤的一种描述，是若干条指令组成的有穷序列。

算法就是”解决问题的方法步骤”。

完整例子：求连续自然数和

问题： 求 $a_1, a_2, \dots, a_n$ 共 $n$ 个连续自然数的和。

• 输入：$a_1$、$n$
• 输出：从 $a_1$ 开始的 $n$ 个连续自然数的和 $sum$
• 步骤：从 $a_1$ 开始，累加 $n-1$ 次

算法的五大基本特性#

注意

可行性 意味步骤必须是”现实可实现”的，不能出现无法实现的操作；确定性 + 有穷性 是算法能有效运行的关键。

算法 vs 程序#

核心区别

程序可以不满足有限性。例如操作系统是持续运行的程序，需要不断响应用户操作，无法在有限步内终止；而算法必须终止。

伪代码约定#

练习1：最大公约数 gcd（辗转相除法）

1
算法：gcd(m, n)
2
输入：非负整数 m, n（不全为 0）
3
输出：m 与 n 的最大公约数
4
1. while m > 0 do
5
2.    r ← n mod m
6
3.    n ← m
7
4.    m ← r
8
5. return n

练习2：顺序查找 Search

1
算法：Search(L, x)
2
输入：数组 L[0..n]，元素 x
3
输出：若存在返回位置，否则返回 -1
4
1. i ← 0
5
2. while (i < n) do
6
3.    if (L[i] = x) then
7
4.       return i
8
5.    i++
9
6. return -1

算法设计的一般过程#

1. 充分理解要解决的问题
2. 问题建模（输入、条件、目标）
3. 选择算法设计策略
4. 算法描述
5. 算法的正确性验证（若存在反例，找出来）

建模与数据结构的关系

问题建模是把现实问题转化为计算机可处理模型；数据结构是存储模型数据的载体。建模决定需要什么数据，数据结构服务于模型，反过来约束建模方案。

为什么要做复杂性分析？#

算法复杂性主要指时间复杂性和空间复杂性，分析的是输入规模增大时资源开销的增长趋势，而非单纯算”跑多少秒、占多少内存”。

• 机器无关，评价算法本身优劣
• 预判大规模数据下程序会不会失效（最重要现实意义）
• 指导算法设计与选择，做取舍
• 区分”能跑通”和”高效”

算法的性质（评价指标）#

时间复杂性的三种情况#

影响时间复杂性的因素：问题规模 $N$、输入实例 $I$、算法本身 $A$。

渐近性态#

当 $N \to \infty$ 时，若 $\dfrac{T(N) - \Phi(N)}{T(N)} \to 0$，则 $\Phi(N)$ 是 $T(N)$ 的渐近性态。

渐近性态简化了复杂性分析：只要关注阶，忽略常数因子。

例子

• $T_1(n) = 30n^4 + 20n^3 + 40n^2 + 46n + 100 \approx n^4$
• $T_2(n) = 1000n^3 + 50n^2 + 78n + 10 \approx n^3$

$n$ 很大时，算法 A 是 $n^4$，算法 B 是 $n^3$。

渐近记号 O / Ω / Θ / o#

核心理解

$O(g(n))$ 是一个函数集：其中每个函数 $h(n)$ 都满足 $h(n) \le c \cdot g(n)$（$c$ 为常数，$n \ge 1$）。

上界越低、下界越高，评估越精确。

O(n) 复杂度的判断（重要）

• $\log n$、$n \log n$、$1000n^2$、$10n^2+100n$ 都是 $O(n^2)$ 的
• $O(n) = O(n^2)$ ✓ （$n$ 是 $n^2$ 的子集，同集关系）
• $O(n^2) = O(n)$ ✗ （$n^2$ 不可能是 $n$ 的上界）

O 记号的性质#

• $O(f) + O(g) = O(\max(f, g))$
• $O(f) + O(g) = O(f + g)$
• $O(f) \cdot O(g) = O(fg)$
• 若 $g(n) = O(f(n))$，则 $O(f) + O(g) = O(f)$
• $O(Cf(n)) = O(f(n))$（$C$ 为正常数）
• $f = O(f)$

常见复杂度形态（从快到慢）#

注意

不同复杂度在 $n$ 增大时差距巨大。$O(n \log n)$ 与 $O(n^2)$ 在数据量达到百万级时可能相差数万倍。

计算复杂性理论#

研究计算问题本身有多难（需要多少资源、分属于哪个难度类），而非某个具体程序怎么写。标准计算模型是图灵机。

问题分类#

关键关系

• $P \subseteq NP$（P 中的判定问题也在 NP 中）
• P = NP 猜想：P 类是否等于 NP 类，是计算机科学重大问题，至今未解决
• 若某 NP-hard 问题 $Q$ 能在多项式时间求解，则 P = NP
• 若 $P \ne NP$，则 NP 难问题都不能在多项式时间求解

典型 NP 问题#

SAT（布尔可满足性，Satisfiability）——计算机科学最重要的问题：

给定一个合取范式（CNF）$F = F(x_1, x_2, \dots, x_n)$，是否存在一组布尔赋值 $x_1\dots x_n \in \{0,1\}$ 使得 $F = True$？

IS（独立集问题，Independent Set）——第二重要的问题：

给定图 $G$ 和整数 $k$，能否在 $G$ 中找 $k$ 个点，使其中任意两点不相邻？

判定问题 vs 优化问题

讨论中一般关注判定问题（decision problems）：证明解的存在性不难。给定了 $k$ 个点的集合 $I$（或一组赋值后），很容易判定 $I$ 是不是独立集（或 CNF 是否可满足）。

判定问题与其对应的优化问题通常具有相似的复杂度，因此重点研究判定问题。

NP 完全问题#

• Cook 定理：布尔表达式的可满足性问题（CNF-SAT、3-SAT）是第一个 NP 完全问题
• 多项式时间变换：NP 完全问题可在多项式时间内互相转换，因此可用已知 NPC 问题证明其他问题的复杂性