第一部分：算法分析基础与开发规范 (Foundations & Methodology)

1.1 算法核心概念 (Core Concepts of Algorithms)

1.1.1 算法的定义与本质 (Definition & Nature)

算法是执行特定任务的一组指令集（A set of instructions for performing a task）。程序通常会输入（Input）必要的数值，以正确的方式进行处理，然后将结果输出（Output）给用户。因此，程序通常被看作算法 （alogorithm）和数据（data）的结合。

算法的静态与动态

  • 静态 (Static)： 算法在纸面或代码中由作者编写的形式。
  • 动态 (Dynamic)： 算法被处理器（Processor）执行时的过程。

算法的四个核心特征

  1. 清晰且可执行 (Clear and Executable)： 每一条指令必须明确无歧义，且能够被执行。
  2. 确定性 (Determinate)： 在任何给定状态下，下一步的操作必须是唯一的，不存在二义性。
  3. 有穷性 (Terminate)： 算法必须在有限的步骤内结束，不能陷入无限循环。
  4. 目标达成 (Goal Achieved)： 过程结束后，必须产生预期的结果或输出。

算法的结构要素

现代算法通常包含以下逻辑结构：

  • 声明 (Declarations)： 对涉及的对象（数据）进行定义。
  • 指令序列 (Sequential Instructions)： 按顺序执行的操作。
  • 决策/分支 (Decisions)： 根据当前状态选择执行路径（如 if-then-else）。
  • 重复/迭代 (Repetition/Iteration)： 多次执行某些部分（如 loops），直到满足特定状态（如“烤到表面金黄”）。
  • 过程/方法 (Procedures/Methods)： 将一组指令封装为子算法（Sub-algorithm），用于解决子问题。

1.1.2 算法分析 algorithms analysis

算法分析的目的子啊与改进算法和选择算法。在设计或选择算法时，通常从以下五个维度进行评估：

  • 正确性（Correctness）：算法是否能得到预期结果。

  • 工作量（Amount of Work Done）：通常指时间复杂度（Time Complexity）。

  • 空间占用（Amount of Space Used）：通常指空间复杂度（Space Complexity）。

  • 简单性（Simplicity）：算法是否易于理解、实现和维护。

  • 最优性（Optimality）：该算法是否已经是解决该类问题的效率极限。

正确性 Correctness

一个算法是正确的，是指当给定合法输入时，它能在有限的时间内运行结束并产生正确的答案。

正确性的证明方法包括：非正式方法（检查细节和手动模拟），模块化分解和数学归纳法

以顺序查找（Sequential Search）为例：

其精确的正确性陈述：给定一个包含 $n$ 个元素（$n \geq 0$）的数组 $L$ 和目标值 $X$，顺序查找算法在终止时：若 $X$ 存在，则 $j$ 为 $X$ 在 $L$ 中第一次出现的索引；否则 $j = 0$。

其伪代码为：

1
2
3
4
5
6
7
8
Algorithm Sequential search
Input: L,n,X (search X in L, where L is an array with n entries)
Output: l (indice of X in L)
j <- 1
while j<=n and L(j)!=X
    do j <- j+1
end while do
if j>n then j <- 0

证明

为了应用归纳法，我们需要证明一个更强的命题。
命题： 对于 $1 \leq k \leq n+1$，当控制流第 $k$ 次到达第 2 行的测试时，满足以下条件：

  • $j = k$，且对于所有 $1 \leq i < k$，均有 $L(i) \neq X$。
  • 若 $k \leq n$ 且 $L(k) = X$，算法将在执行测试和第 4 行后终止，且 $j$ 仍等于 $k$。
  • 若 $k = n+1$，算法将在执行测试和第 4 行后终止，且 $j = 0$。
    证明步骤：
  • 基础步骤（Base Case, $k = 1$）：
    • 根据第 1 行，$j = 1 = k$。由于没有 $i < 1$ 的情况，条件 1 的第二部分自然成立。
    • 若 $1 \leq n$ 且 $L(1) = X$，第 2 行测试失败，跳至第 4 行，由于 $j = 1 \leq n$，$j$ 保持不变，符合条件 2。
    • 若 $k = n+1$（即 $n=0$，空列表），$j=1$，第 2 行测试失败，第 4 行将 $j$ 设为 $0$，符合条件 3。
  • 归纳假设（Inductive Step）：假设命题对某个 $k < n+1$ 成立，证明其对 $k+1$ 也成立。
    当控制流第 $k+1$ 次到达第 2 行测试时：
    • 关于条件 1：由于此前第 $k$ 次测试成功（即 $L(k) \neq X$）并执行了第 3 行的 $j \leftarrow j+1$，故当前 $j = k+1$。根据假设，已知 $1 \leq i < k$ 时 $L(i) \neq X$，结合 $L(k) \neq X$，得出对于 $1 \leq i < k+1$，$L(i) \neq X$ 成立。
    • 关于条件 2 和 3：逻辑推导与基础步骤类似，若在 $k+1$ 处找到匹配或达到边界，算法将按预期在第 4 行处理 $j$ 的最终值。

通过证明，我们可以得出：第 2 行的测试最多执行 $n+1$ 次。输出 $j=0$ 当且仅当 $X$ 不在 $L$ 中。输出 $j=k$ 当且仅当 $k$ 是 $X$ 第一次出现的索引。因此，该算法是正确的。

工作量 amount of work done

为了排除硬件差异，通常通过计算基本操作的执行次数（Number of Basic Operations Done）来评估效率。为了简化计算，我们通常假定一条编程语句等同于一个时间单位。

运行时间的分类程序的运行时间不仅取决于输入规模，还取决于输入的具体内容。因此，我们将运行时间进一步分类：

  • 最坏情况（Worst Case, $T_{worst}(n)$）：算法在任何规模为 $n$ 的输入上执行的最大操作次数。它最容易计算，且具有重要的实际指导意义。
  • 平均情况（Average Case, $T_{avg}(n)$）：在所有可能输入情况下的期望执行次数。
  • 最好情况（Best Case, $T_{best}(n)$）：执行次数最少的情况，实际应用中较少使用。

考虑伪代码：

1
2
3
4
5
6
7
8
9
10
11
Algorithm FINDMAX
Input: L, n
Output: max

max<- a[0]
for i = 1 to n
    if a[i] > max
        max = a[i]
    end if
    i <- i+1
end for

易见

情况类型 (Case Type) 执行逻辑描述 (Logic Description) 计算公式 (Formula) 最终结果 $T(n)$
最坏情况 (Worst Case) 数组递增（如 {1,2,3,4}），每次 if 都为真，都要执行赋值。 $1(max初值) + 2(for初值+首次测试) + 4(n-1)$ $4n - 1$
平均情况 (Average Case) 假设平均每隔一个元素更新一次 max。 $3 + 3(n-1) + \frac{n-1}{2}$ $3.5n - 0.5$
最好情况 (Best Case) $a[0]$ 即为最大值，if 后的赋值从未执行。 $3 + 3(n-1)$ $3n$

时间复杂度

  • 平均情况（Average Case）设 $D_n$ 为规模为 $n$ 的所有可能输入的集合，$I$ 是其中的一个元素。
    • $p(I)$ 是输入 $I$ 出现的概率。$t(I)$ 是算法处理输入 $I$ 时执行的基本操作次数。平均行为 $A(n)$ 定义为：
    • $t(I)$ 可以通过分析算法得出，但概率 $p(I)$ 通常难以分析确定，通常需要经验数据或特定应用背景。
  • 最坏情况（Worst Case）最坏情况 $W(n)$ 定义为所有输入中操作次数的最大值：

以顺序查找为例

平均行为分析：设 $q$ 为目标元素 $X$ 在列表中的概率，并假设 $X$ 出现在列表任意位置的概率相等（即 $q/n$）。若 $X$ 在第 $i$ 个位置，比较次数为 $i$。若 $X$ 不在列表中（概率为 $1-q$），比较次数为 $n$。

因此，计算公式显然为：

最坏情况分析：当 $X$ 位于列表最后一个位置，或者 $X$ 完全不在列表中时，算法需要扫描所有元素。

时间复杂度作为一个量化指标，常用于对比算法
如：

算法 A 和算法 B：

  • $T_a(n) = 2n^2$
  • $T_b(n) = 100n$

当 $n$ 较小时（例如 $n=10$），算法 A ($T=200$) 优于算法 B ($T=1000$)。当 $n$ 较大时（例如 $n=100$），算法 B ($T=10,000$) 远优于算法 A ($T=20,000$)。计算得交点为$n = 50$。

大O表示法

大O表示法允许我们在评估程序的运行时间时忽略常数。更精确地说，如果存在 $n_0 \le n$ 且 $c > 0$，使得 $T(n) \le c f(n)$ 成立。，则$T(n) = O(f(n))$。

考虑 $T(n) = (n+1)^2$。在这种情况下，我们可以说 $T(n)$ 是 $O(n^2)$。因为：$n^2 + 2n + 1 \le n^2 + 2n^2 + n^2 = 4n^2$

大O表示法 (Big-Oh) 非正式名称 (Informal Name)
O(1) 常数阶 (constant)
O(log n) 对数阶 (logarithmic)
O(n) 线性阶 (linear)
O(n log n) n log n 阶
O(n^2) 平方阶 (quadratic)
O(n^3) 立方阶 (cubic)
O(2^n) 指数阶 (exponential)
O(n!) 阶乘阶 (factorial)

除此之外还有其他渐进复杂度符号：

  • Ω-符号（$\Omega$-notation）：如果函数 $t(n)$ 被 $g(n)$ 的某个常数倍从下方限定（Bounded below），则称 $t(n)$ 属于 $\Omega(g(n))$，记作 $t(n) \in \Omega(g(n))$。即：如果存在某个正数常数 $c$ 和某个非负整数 $n_0$，使得对于所有 $n \ge n_0$，有：

  • Θ-符号（$\Theta$-notation）：如果函数 $t(n)$ 对于所有足够大的 $n$，同时被 $g(n)$ 的正数常数倍从上方和下方限定，则称 $t(n)$ 属于 $\Theta(g(n))$，记作 $t(n) \in \Theta(g(n))$。即：如果存在正数常数 $c_1$ 和 $c_2$ 以及某个非负整数 $n_0$，使得对于所有 $n \ge n_0$，有：

除此之外还有相对并不常用的两个非紧确上下界：o，$\omega$

运算法和数学性质

  • $O(f(n)) + O(g(n)) = O(\max{f(n), g(n)})$
  • $O(f(n)) + O(g(n)) = O(f(n) + g(n))$
  • $O(f(n)) \times O(g(n)) = O(f(n) \times g(n))$
  • $O(c f(n)) = O(f(n))$
  • 传递性（Transitivity）：若 $f(n) = O(g(n))$ 且 $g(n) = O(h(n))$，则 $f(n) = O(h(n))$。同样适用于 $\Omega$ 和 $\Theta$。
  • 对称性（Symmetry）：$f(n) = \Theta(g(n)) \iff g(n) = \Theta(f(n))$。
  • 转置对称性（Transpose Symmetry）：$f(n) = O(g(n)) \iff g(n) = \Omega(f(n))$。
  • 自反性（Reflexivity）：$f(n) = \Theta(f(n))$；$f(n) = O(f(n))$；$f(n) = \Omega(f(n))$。

空间占用量

即空间复杂度：程序使用的内存单元（Memory cells）数量。其重要性体现在：

  • 预测运行程序所需的内存空间是否足够。

  • 在多用户系统中为程序分配内存。

  • 估算算法能够解决的问题规模。

所有关于时间复杂度的增长阶和渐近界限定义均适用于空间复杂度。显然，辅助工作空间不会超过算法的运行时间，因为向每个内存单元写入数据至少需要常数时间。

若 $t(n)$ 和 $s(n)$ 分别表示算法的时间和空间复杂度，则：

简洁性（Simplicity）

通常情况下，解决问题最简单、最直接的方法往往不是最高效的。然而，算法的简洁性是一个非常理想的特性：

它使验证算法的正确性变得更容易。

它使程序的编写、调试和修改更加容易。 在选择算法时，应考虑开发调试程序所需的时间；但如果程序会被频繁使用，其效率通常是决定性的因素

最优性（Optimality）

如果在研究的同类算法中，没有其他算法在最坏情况（Worst case）下执行的基本操作（Basic operations）更少，则称该算法是最优的。

通常不需要逐个分析同类中的每一个算法。通常可以证明关于下界的定理，确定解决该问题所需的最小操作次数。任何达到该下界操作数的算法即为最优算法。

示例：寻找 $n$ 个数中的最大值

  • 上界（Upper bound）：
    算法 FINDMAX 依次比较元素。比较操作在第 3 行执行，共执行了 $n-1$ 次。因此，$n-1$ 是最坏情况下寻找最大值所需比较次数的一个上界。

  • 下界（Lower bound）：
    假设列表中的元素各不相同。在 $n$ 个不同的元素中，有 $n-1$ 个元素不是最大值。只有当一个元素小于至少一个其他元素时，我们才能断定它不是最大值。因此，这 $n-1$ 个元素必须在算法的比较中成为“输家”。由于每次比较只能产生一个输家，因此至少必须进行 $n-1$ 次比较。
    得出结论：$F(n) = n-1$ 是所需比较次数的下界。

结论： 由于上界与下界相等（均为 $n-1$），FINDMAX 算法是最优的。

1.1.3 算法设计流程

算法开发的完整流程（Complete Development of an Algo.）

一个算法从构思到落地的过程通常包含以下八个核心阶段：

  • 问题陈述（Statement of the problem）

  • 模型建立（Development of a Model）

  • 算法设计（Design of the algorithm）

  • 算法正确性验证（Correctness of the algorithm）

  • 实现（Implementation）

  • 算法分析与复杂度（Analysis and complexity of the algorithm）

  • 程序测试（Program testing）

  • 文档编制（Documentation）

1.2 算法开发示例：最小费用通讯网络构建

任务背景（The Task） 决策是否在不同站点（Sites）之间建立计算机网络。需考虑的因素包括：

  • 各站点可用的计算资源；

  • 预期的站点使用水平；

  • 系统的峰值需求（Peak demands）；

  • 主要设施可能出现的系统性能退化（System degradation）；

  • ……

  • 拟建网络的成本（The cost of the proposed network）。

其中

拟建网络的成本主要包括：

  • 设备采购费用；
  • 通讯链路（Communication links）的建立费用；
  • 系统维护费用；
  • 在特定站点运行特定类型作业的成本。

在分析租用线路成本时，需考虑：

  • 站点间的地理距离；
  • 所需的传输速率（Transmission rate）；
  • 线路所需的传输容量。

经过讨论，我们得到了站点 $i$ 与 $j$ 之间的成本 $C_{ij}$，这是一个对称成本矩阵（Symmetric cost matrix）。

1.2.1 问题陈述与建模 (Problem Statement & Modeling)

问题陈述

在已知网络中任意两点间建立链路的花费$C_{ij}$的前提下，需要建立一个最小费用的通讯网络，使得网络中任何站点之间都可以相互通讯。

模型建立

最终的解将由原始成本矩阵 $C$ 修改后的矩阵 $C’$ 构成：如果不建立链路，则 $(i, j)$ 和 $(j, i)$ 的条目等于 $\infty$。如果建立链路，则条目等于 $C_{ij}$。[为什么不是0呢]。

解并不难定义，问题在于连接性约束。我们先来考虑第一种可能

约束v1：$C’$ 的每一行和每一列至少会有一个有限值（Finite entry）。

显然，这个约束并不能保证连通性。如果我们在这个基础上修改，约束可以变成：

约束v2：$C’$ 的每一行和每一列至少会有一个有限值（Finite entry），且每个有限值的上下左右至少有两个非无穷元素。

然而即便如此，图可能被分割成几个孤立的“岛屿”（例如 A-B 互连，C-D 互连，但 AB 与 CD 不通）。这将约束导向：

约束v3：$C’$ 的每一行和每一列至少会有一个有限值（Finite entry），且整个图是一个单一的连通分量。

除此之外，还应该考虑，图应该是无环的，如果图中包含环，那么通过移除该环中成本最高的链路，可以找到一个成本更低的解。由此，约束可以写成：

约束v4：含所有顶点（即前文中的有限值约束）、连通且无回路

这将这个问题的解导向为生成树（即满足以上条件的子网络）。

数学化描述

给定一个加权连通网络（Weighted, connected network） $C$，寻找 $C$ 的一个最小生成树（Minimum-cost spanning tree, MCST / MST）。

模型（Model）：设 $C=(V, E)$ 是一个连通无向图；$w(u, v)$ 是连接顶点 $u, v \in V$ 的成本；寻找一个无回路的子集 $T \subseteq E$，它连接 $V$ 中的所有顶点，且使得权值之和最小：

1.2.2 算法设计演进：从直觉到 Prim 算法 (Design Evolution)

贪心算法

由此，可以提出第一种出于直觉的算法

1
2
3
4
5
6
7
8
9
10
11
Algorithm A_GREEDY
Input: C, N
Output: T (minimum-weight spanning tree T)
T <- a network consisting of N vertices and no edges(a 2-dim array where all elements are infinite.)
H <- C
while T is not a connected network 
    Get (U,V) the lightest edge in H;
    if T+(U,V) has no cycles
    then set T <- T + (U,V)
    end if
    Set H <- H - (U,V)

算法检查：

  • 算法A一定会停止，H中的有限条边总会被完全移除
  • 停止时，T总是C的生成树，前提是C本身是联通的
  • T是最小生成树。图论证明指出，对于图中的任意切割（将顶点分为两部分），横跨该切割的最小权重的边一定属于某个最小生成树。算法 A 的逻辑隐式地利用了这一性质，确保每次选择的都是当前安全且成本最低的边。因此，最终生成的 $T$ 权值之和 $w(T)$ 是最小的。
  • 算法A不是自包含的，连通性检查和回路检测都未实现。
  • 算法A效率极低，总的时间复杂度可能接近于O(MN)

证明横跨切割的最小权重边一定属于某个最小生成树
设 $G = (V, E)$ 是一个连通加权无向图。将顶点集合 $V$ 划分为两个不相交的集合 $(S, V-S)$。横跨边为任何一条连接 $S$ 中顶点和 $V-S$ 中顶点的边。设 $e = (u, v)$ 是横跨该切割的所有边中权重最小的一条。
证明：边 $e$ 必定包含在图 $G$ 的某棵最小生成树（MST）中。

假设 $T$ 是图 $G$ 的一棵最小生成树，但 $e \notin T$。
由于 $T$ 是生成树，它包含连接 $V$ 中所有顶点的路径。因此，在 $T$ 中必然存在一条唯一的路径连接 $u$ 和 $v$。
当我们把边 $e = (u, v)$ 加入到 $T$ 中时，这就形成了一个回路。
记这个新图为 $T + {e}$。
由于 $u \in S$ 且 $v \in V-S$，连接 $u$ 和 $v$ 的那条路径必须从集合 $S$ 跨越到集合 $V-S$。
这意味着，在 $T$ 中连接 $u$ 和 $v$ 的路径上，至少存在另一条边 $e’$ 也横跨了切割 $(S, V-S)$。
$e$ 是横跨该切割的权重最小的边。因此，我们可以得出结论：
从图 $T + {e}$ 中移除边 $e’$。
由于 $e’$ 处于回路中，移除它并不会破坏图的连通性。同时，图的顶点数不变，边数恢复为 $N-1$。因此，我们得到了一棵新的生成树 $T’ = (T \setminus {e’}) \cup {e}$。
有
$T’$ 必定也是一棵最小生成树

Prim 算法

如果我们能发现一种构建生成树的方法，能够自动保证生成的网络既连通又无回路，而无需每次进行显式检查，那么算法 A 就能得到改进。

回忆之前对约束的描述。考虑向部分解中添加边，为了保证联通，需保证边的一个端点属于当前部分解。为了保证无环，需保证另一个端点不再当前部分解中。

由此，可以写出算法B：

Algorithm PRIM
T <- a network consisting N vertices and no edges
Q <- all vertices in C
U <- a random vertice in Q
Q.pop(U)
while len(Q) != 0
V <- the vertex for which (U,V) is the shortest edge connected to U
T <- T + (U,V)
U <- Q.pop(V)
end while

这个算法大体上是自包含的，且比A更高效

Prim算法的正确性验证

定理 1 (Theorem 1)
在算法 B 的步骤 2 每次执行完成时，当前 $T$ 中的边在当前已选顶点集上构成一棵树。

  • 若 $K = 1$，则存在两个已选顶点和 $T$ 中连接它们的一条边，显然构成树。
  • 假设在执行 $K$ 次后，当前 $T$ 中的边在已选顶点上构成一棵树，记为 $T_c$。
  • 考虑第 $(K + 1)$ 次执行：这本质上是向 $T_c$ 添加一个新顶点和一条新边。由于这条新边是连接该新顶点与 $T_c$ 的唯一边，因此不会在 $T_c$ 中产生回路（Cycle），且保持了连通性。
  • 因此，$T_c$ 仍然是一棵树。

定理 2 (Theorem 2)
在算法 B 结束时，$T$ 是 $G$ 的一棵生成树（Spanning tree）。
显然

定理 3 (Theorem 3)
记 $T$ 是网络 $G$ 的一个子树，且令 $e$ 为连接 $T$ 中节点与不在 $T$ 中节点的最轻边。则 $G$ 中存在一棵包含 $T$ 和 $e$ 的生成树 $T’$，使得对于任意包含 $T$ 的生成树 $T’’$，都有 $W(T’) \le W(T’’)$。
同之前的贪心算法中的证明

定理 4 (Theorem 4)
设 $G = (V, E)$ 为加权连通网络，$e = (v, w)$ 是关联于顶点 $v$ 的最轻边。则存在一棵包含 $e$ 的最小生成树（MST）$T$。

  • 设 $T$ 是不包含 $e$ 的 MST。考虑 $T \cup {e}$，它恰好包含一个环。该环包含两条关联于 $v$ 的边，即 $e = (v, w)$ 和另一条边 $f = (u, v)$。根据题设 $w(e) \le w(f)$，故 $(T - {f}) \cup {e}$ 也是包含 $e$ 的 MST。

定理 5 (Theorem 5)
算法 B 能够找到加权连通网络 $G$ 的一棵最小生成树 $T$。

  • 根据定理 2，算法 B 找到一棵生成树。
  • 根据定理 4，存在包含算法 B 所选第一条边 $e_1$ 的 MST $T_1$。
  • 根据定理 3，存在包含 $e_1$ 和 $e_2$ 的生成树 $T_2$，且其权值在所有包含 $e_1$ 的生成树中最小；即 $W(T_2) = W(T_1)$，因此 $T_2$ 也是 MST。
  • 通过重复此过程，定理 3 保证了对于所有 $k = 1, 2, \dots, N-1$，都存在包含算法 B 所选前 $k$ 条边的 MST。
  • 最终得到的 $W(T_{N-1}) = W(T_1)$。

一种改进技术

之前我们说这种算法基本自包含，是因为这种算法并没有规定the vertex for which (U,V) is the shortest edge 是如何选择的。

可以将伪代码扩展为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Algorithm PRIM-C
Input G,C a weighted, connected network with N vertices and M edges , and a cost matrix C[i,j]
Output T

T <- a network consisting N vertices and no edges
UNCHSH <- all vertices in C
NUMUN <- N

UNCHSN[1] <- UNCHSN[NUMUN] # 覆盖
NUMUN <- NUMUN - 1

for I from 1 to NUMUN:
    TargetNode <- UNCHSN[I]
    LIGHT[I] <- C[StartNode, TargetNode]  
    VERTEX[I] <- StartNode             

while NUMUN > 0
    K <- argmin(LIGHT[1..NUMUN])
    V <- UNCHSN[K]
    U <- VERTEX[K]
    T <- T + (U,V)
    if K != NUMUN:
        UNCHSN[K] <- UNCHSN(NUMUN)
        LIGHT[K] <- LIGHT(NUMUN)
        VERTEX[K] <- VERTEX[NUMUN]
    end if
    NUMUN <- NUMUN - 1
    for I < NUMUN:
        if C(V,UNCHSN[I]) < LIGHT[I]
            LIGHT[I] = C(V,UNCHSN[I])
            VERTEX[I] = V
        end if 
    end for
end while

算法 C 是算法 B 的高效实现版本。由于其逻辑严格遵循了定理 1 至定理 5 的证明过程，因此它能够保证找到加权连通图的最小生成树。

时间复杂度

分析其时间复杂度：

  • 初始化：O(N)
  • 寻找最轻边：第 $i$ 次迭代需要比较 $N-i$ 个元素。总计 $\sum_{i=1}^{N-1} (N-i) = \frac{N(N-1)}{2}$ 次比较。
  • 更新 LIGHT 数组：同上，总计约 $\frac{N(N-1)}{2}$ 次比较与更新
  • 总算法复杂度：

因此，这种算法的时间复杂度与边数无关，非常适合稠密图。

实际上，其复杂度 $O(N^2)$ 在渐近意义上达到了读取输入数据的下界，因此在处理稠密图时是具有最优性的。

后续的工作包括程序测试和文档编制，在此不再涉及。

1.2.3 Kruskal 算法

虽然 Prim 算法在稠密图中表现优异，但一种被称作 Kruskal 的算法配合高效的不相交集合（Disjoint Set）数据结构，在边数较少时效率极高。

1
2
3
4
5
6
7
8
9
10
11
12
13
Algorithm Kruskal
A <- ∅
for vertex in all vertices of G
    MAKE_SET(vertex)
end for
Sort edges by weight
for edge in all edge of G
    if FIND_SET(u) != FIND_SET(v) // if u and v don't belong to the same set
        A <- A ∪ {(u, v)}
        UNION(u,v)
    end if
end for

这种算法很好理解，使用了排序保证了最小，使用了集合操作保证了连通性和无环性。

这种算法速度的关键在于集合的维护。如果使用链表方式维护集合，并且使用加权合并启发式策略，始终将较短的链表连接到较长的链表之后，最终的时间复杂度为O(m+nlog(n))。

最快的实现方式是使用不相交集合森林。这种方法使用树来表示集合。

这种树种每个节点代表集合中的一个成员，每个节点仅包含一个指向父节点的指针，根节点的父节点指向自己。为了避免树退化为一条长链，为每棵树维护一个rank，表示该树的一个高度上街。在合并时，使用保证rank小的树指向rank大的数的树根。

  • 如果两棵树 rank 不同：大树吞并小树，新根的 rank 不变。

  • 如果两棵树 rank 相同：任意合并，但新根的 rank 必须加 1。

如此，包含 $n$ 个节点的树，其高度最多为 $\lfloor \log_2 n \rfloor$。

这种算法的时间复杂度是$O(m \cdot \alpha(m, n))$，可以近似认为O(mlogm)。

对于森林的操作，可以参照以下伪代码，关注其中的路径压缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Algorithm MAKE_SET(x)
p[x] <- x // the root node is x, that mean the parent node of x is x
rank[x] <- 0

Algorithm FIND_SET(x)
if x != p[x]
    p[x] <- FIND_SET(p[x])
    // To find the root of element x in this tree, we follow the parent pointers from x upwards. If x is not the root, we recursively find the root of its parent. During this search, we apply path compression by updating the parent of each visited node directly to the root once it is found.
end if

Algorithm UNION(x,y)
if rank[x] > rank [y]
    p[y] <- x
else p[x] <- y
    if rank[x] = rank[y]
        rank[y] <- rank[y]+1
    end if
end if

因此，通常Kruskal 算法：$O(E \log E)$，更适合稀疏图（Sparse graphs）。Prim 算法 (算法 C)：$O(V^2)$，更适合稠密图（Dense graphs）。

1.2.4 基于优先队列的Prim算法

为了提高 Prim 算法的效率，关键在于如何快速选择要添加到当前部分解（集合 $A$）中的新边。我们可以使用优先队列（Priority Queue）来实现这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Algorithm PRIM-D
Q <- V[G]   // put all of vertex in priority queue
for u in Q
    key[u] <- infinity  
end for
key[r] <- 0
Pi[r] <- Null
while Q is not empty
    u <- EXTRACT_MIN(Q) // extract the vertex with the minimum key from the queue
    for v in Adj[u]
        if v in Q and w(u,v) < key[v]
            Pi[v] <- u
            key[v] <- w(u,v)
        end if
    end for
end while

这种Prim算法只会维护一颗单一的树，算法不断寻找与树相连但尚未加入树的顶点中，最近的一个。
由于EXTRACR_MIN的特性，key值越小的Q中的元素，越早被弹出。

第一步，由于只有key[r]被设置为0，因此一定会弹出r。然后，程序会考察所有r的相邻元素的key值。如此，不断重复，key值中始终储存的是到达已经生成的树的最短距离。

这与Prim-C的算法实际上很像。回忆，Prim-C的算法维护了一个Light数组和一个Vertex数组，用于记录每个节点与当前树的最短路径和最短距离。
C算法的每一条边都是从生成树上的某个节点（储存在VERTEX中的某个元素），向最近的节点连接；而D算法使用了父节点来保证这样的连接。即，VERTEX中储存的元素，如今被储存在Pi中。唯一不同的是，C算法每一步需要在LIGHT中搜索最小值，D算法使用堆等数据结构给出最小值。

还有一点是，C算法通常要求（或者说形式上假设了，因此在这种情况下也比较有利）图是稠密的，即所有节点两两相连，即C算法通常依赖于一个邻接矩阵C使用；D算法通常配合邻接表使用，不要求所有节点两两相连。

根据使用的堆的实现方式，D算法的效率也有所不同：

  • 二叉堆（Binary Heap）：
    • EXTRACT-MIN 耗时 $O(\log V)$。
    • DECREASE-KEY（更新 key 值）耗时 $O(\log V)$。
    • 总复杂度：$O(E \log V)$。
  • 斐波那契堆（Fibonacci Heap）：
    • DECREASE-KEY 摊还时间为 $O(1)$。
    • 总复杂度：$O(E + V \log V)$，这是目前理论上最快的实现。

当然，如果图本社是稠密的，$E \approx V^2$，D算法与C算法的时间复杂度相差不大。

二叉堆 Binary Heap

二叉堆是一种基于数组的数据结构，逻辑上被视作一棵近似完全二叉树（除了最底层之外，每一层都是满的）。对于下表为i的节点，其父节点下表为(i-2)/2，左右子节点下标为(2i+1),(2i+2)

由于堆是完全的，包含n各元素的堆高度严格固定为 $\lfloor \log_2 n \rfloor$。堆的所有核心操作（如插入、删除、修改键值）的时间复杂度都与树高成正比，即 $O(\log n)$。这比简单的数组扫描（$O(n)$）要快得多。

包括以下操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Algorithm HEAPIFY(A,i)
// The function of HEAPIFY is to let the value of A[i] "float down" within the heap, thereby ensuring that the subtree rooted at index i satisfies the heap property.
l <- LEFT[i]
r <- RIGHT[i]
// the heapift operation at index i only affects the subtree rooted at i
if l<=heap-size[A] and A[l]>A[i]
    largest <- l
else
    largest <- i
end if
if r<=heap-size[A] and A[r]>A[largest]
    largest <- r
end if
if largest != i
    exchange A[i] and A[largest]
    HEAPFY(A,largest)
end if

对于二叉堆，大的元素应该尽可能接近树根。因此只需要比较i与左右子节点，将最小的子节点（或者自己），下沉，再对下沉后的子节点重排即可。

1
2
3
4
5
Algorithm BUILD-HEAP(A)
heap-size[A] <- length[A]
for i <- length[A]/2 down to 1
    HEAPIFY(A,i)
end for

即堆排序。这与完全堆的性质有关。length[A]/2一定是最后一个“叶节点的父节点”。

对于提取最大值，直接选择第一个元素，然后再重排1即可。