算法理论知识点

典型 P 类问题：

• 排序问题 — O(n log n)
• 最短路径（Dijkstra）— O(V^2) 或 O(E + V log V)
• 最大匹配（二分图）— O(VE)
• 线性规划 — 多项式时间（内点法）
• 素性测试 — O(log^6 n)（AKS 算法）

NP 类（Nondeterministic Polynomial Time）

NP 类包含所有可以在非确定性图灵机上用多项式时间求解的判定问题。等价定义：给定一个候选解，可以在多项式时间内验证其正确性。

典型 NP 类问题：

• 旅行商问题（TSP）— 判定版
• 子集和问题 — 给定整数集合，是否存在子集和为 K
• 图着色问题 — 能否用 k 种颜色给图着色
• 布尔可满足性问题（SAT）— 是否存在赋值使公式为真
• 背包问题 — 判定版

注意：P 是 NP 的子集（P ⊆ NP），因为能在多项式时间内求解的问题当然也能在多项式时间内验证。

NP-Hard

NP-Hard 问题是指至少和 NP 中最难的问题一样难的问题。形式化：如果所有 NP 问题都可以在多项式时间内归约到问题 H，则 H 是 NP-Hard 的。NP-Hard 问题不一定是 NP 问题（可能不在 NP 中）。

NP-Complete

NP-Complete（NPC）问题是既在 NP 中又是 NP-Hard 的问题。NPC 问题是 NP 中最难的问题：如果任何一个 NPC 问题有多项式时间算法，则 P = NP。

NPC 问题的关系：

P ⊆ NP
NP-Hard ∩ NP = NP-Complete

如果 P = NP:
    P = NP = NP-Complete
如果 P ≠ NP:
    P ⊂ NP ⊂ NP-Hard（部分）
    NP-Complete 是 NP 中不属于 P 的部分

多项式归约

证明一个问题是 NP-Complete 的标准方法：

1. 证明该问题属于 NP（给定解可在多项式时间内验证）
2. 选择一个已知的 NP-Complete 问题
3. 构造多项式时间的归约，将已知 NPC 问题转化为该问题
4. 证明归约的正确性（原问题有解 当且仅当 目标问题有解）

经典归约链：

SAT --> 3-SAT --> Clique --> Vertex Cover --> Hamiltonian Cycle --> TSP
     --> 3-SAT --> Independent Set
     --> 3-SAT --> Subset Sum --> Partition --> Knapsack

P vs NP 的意义

P = NP 意味着：

• 所有 NP 问题都有多项式时间算法
• 密码学（RSA、ECC）将不再安全
• 优化问题（调度、路由）可以高效求解
• 数学证明可以自动化验证和发现

目前大多数计算机科学家认为 P ≠ NP，但这仍然是未解决的千禧年数学问题之一。

摊还分析（Amortized Analysis）

什么是摊还分析

摊还分析用于评估一个数据结构中一系列操作的平均代价。与平均情况分析不同，摊还分析不涉及概率，它保证的是最坏情况下每个操作的平均代价。

三种分析方法

1. 聚合分析（Aggregate Method）

计算 n 个操作的总代价上界 T(n)，则每个操作的摊还代价为 T(n)/n。

示例：动态数组的扩容

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None]

    def append(self, value):
        if self.size == self.capacity:
            new_data = [None] * (self.capacity * 2)
            for i in range(self.size):
                new_data[i] = self.data[i]
            self.data = new_data
            self.capacity *= 2
        self.data[self.size] = value
        self.size += 1

分析 n 次 append 操作的总代价：

• 普通插入：O(1) 每次
• 扩容：发生在第 1, 2, 4, 8, 16, … 次插入时
• 扩容总代价：1 + 2 + 4 + … + n/2 < n
• 总代价：n（普通插入）+ n（扩容）= 2n
• 摊还代价：2n / n = O(1)

2. 核算法（Accounting Method）

为不同操作分配不同的摊还代价，使得”昂贵”操作的超额代价由之前”廉价”操作的存款支付。

原则：对于任意操作序列，总摊还代价 >= 总实际代价

动态数组的核算法分析：

• 普通插入：实际代价 1，摊还代价 3（1 用于插入，2 存为存款）
• 扩容插入：实际代价 1 + k（k 为复制元素数），摊还代价 3
  • 之前每个元素存了 2 个单位的存款
  • k 个元素的存款 = 2k，足够支付 k 的复制代价

3. 势能法（Potential Method）

定义势能函数 Φ 将数据结构的状态映射到非负实数。摊还代价 = 实际代价 + ΔΦ。

原则：Φ(D_i) >= 0，Φ(D_0) = 0

动态数组的势能法分析：

• 势能函数：Φ(D) = 2 * size - capacity（当 size > capacity/2 时为正）
• 普通插入：实际代价 1，ΔΦ = 2，摊还代价 = 1 + 2 = 3
• 扩容插入：实际代价 1 + size（复制），ΔΦ = 2 - size（势能从 size 降到 2），摊还代价 = 1 + size + (2 - size) = 3

常见数据结构的摊还代价

斐波那契堆的摊还分析

斐波那契堆通过延迟合并和级联剪切实现高效操作：

• 插入：O(1) — 仅添加到根列表
• 合并：O(1) — 连接根列表
• 减小键值：O(1) 摊还 — 标记+级联剪切，势能函数考虑标记数和树数
• 删除最小：O(log n) 摊还 — 合并根列表，级联剪切保证度数有界

势能函数：Φ(H) = t(H) + 2m(H)，其中 t 为树的数量，m 为标记节点的数量。

竞争分析（Competitive Analysis）

在线算法与竞争比

在线算法（Online Algorithm）在不知道未来输入的情况下逐步做出决策。竞争分析通过将在线算法的代价与最优离线算法（知道全部输入）的代价比较来评估其性能。

竞争比（Competitive Ratio）：如果对于所有输入序列 I，在线算法 ALG 的代价满足：

ALG(I) <= c * OPT(I) + b

其中 OPT(I) 是最优离线算法的代价，c 是竞争比，b 是常数，则称 ALG 是 c-竞争的。

c 越接近 1 越好。c = 1 意味着在线算法与最优离线算法一样好。

经典在线问题

1. 缓存/页面替换（Paging）

问题：缓存容量为 k，收到页面请求序列，缓存未命中时需将页面调入缓存。若缓存已满，需淘汰一个页面。

LRU 的竞争比证明要点：将请求序列划分为 k-相位，每个相位中 LRU 最多产生 k 次未命中，而 OPT 至少产生 1 次未命中。

2. 服务器问题（k-Server Problem）

问题：k 个服务器位于度量空间中的 k 个点，请求序列到达，每次需将一个服务器移动到请求点，代价为移动距离。

k-Server 猜想（已解决）：存在 k-竞争的确定性在线算法。

3. 租借-购买问题（Ski Rental）

问题：每天可以花 1 元租滑雪板，或花 B 元购买。不知道总共滑多少天。

确定性策略的租借-购买分析：

• 如果滑了 < B 天：ALG = 天数，OPT = 天数，比值 = 1
• 如果滑了 >= B 天：ALG = (B-1) + B = 2B-1，OPT = B，比值 < 2

在线算法（Online Algorithm）

在线算法的特点

在线算法必须在不知道未来输入的情况下做出不可撤销的决策。与离线算法的关键区别：

随机化在线算法

随机化可以显著改善竞争比。对于随机化算法，竞争比定义为：

E[ALG(I)] <= c * OPT(I) + b

其中期望是对算法的随机选择取的。

Yao 原理：要证明随机化在线算法的竞争比下界，只需构造一个输入分布，使得任何确定性算法在该分布上的期望代价至少为 c * OPT。

在线算法的应用

1. 操作系统 — 页面替换、磁盘调度
2. 网络 — 路由选择、拥塞控制
3. 金融 — 股票交易、期权定价
4. 云计算 — 虚拟机分配、负载均衡
5. 机器学习 — 在线学习、Bandit 问题
6. 数据流 — 流式算法、频率估计

数据流模型

数据流模型是在线算法的重要应用场景。数据以流的形式到达，算法只能在有限内存中处理，无法存储全部数据。

经典数据流问题：

理论速查表