迁移来源

• 旧站标题：复杂度分析
• 新站标题：图论与组合：讨论班 / 复杂度分析
• 旧站路径：/math/课程/图论与组合/chapters/讨论班/复杂度分析/
• 旧页面 ID：349

复杂度分析

参数与符号 #

设图 $G=(V,E)$ 中顶点数 $|V|=n$、边数 $|E|=m$，顶点 $1$ 的度为 $d_1:=\deg_G(1)=|E_1|$（$E_1$ 为与 $1$ 相邻的边集，$E_0:=E\setminus E_1$）。 在 $V\setminus\{1\}$ 上用 $E_0$ 的 Kruskal（升序）得到最小生成森林 $F_0^{\min}$，其连通块数为 $r$。 记 $\alpha(\cdot)$ 为反阿克曼函数，DSU（并查集）近似视为常数摊还。

基树阶段的代价 #

• 排序与 Kruskal： 对 $E_0$ 排序并运行 Kruskal，时间 $O(|E_0|\log |E_0| + |E_0|\alpha(n)) \subseteq O(m\log m)$。
• 块内最小 $1$-边： 在 Kruskal 过程中/结束后，线性扫描 $E_1$ 为每个块 $C$ 维护 $b_{\min}(C)$，时间 $O(d_1)\le O(m)$。
• 构造基树： 合并 $F_0^{\min}$ 与 $\{b_{\min}(C_i)\}_{i=1}^r$，线性时间。

综上，基树阶段时间 $O(m\log m)$，空间 $O(n+m)$。

“指派”与候选排序的代价 #

在 Kruskal 合并两个块 $A,B$ 的时刻，维护每块的 $m(\cdot)=$ “块内最小 $1$-边权”，并将该次合并边 $e_0$ 指派给 $\max\{m(A),m(B)\}$ 对应的 $1$-边，得到映射 $\mathrm{kill}(\cdot)$。

• 维护 $m(\cdot)$： DSU 合并时用“按秩合并+路径压缩”并携带块信息，摊还 $O(1)$。
• 指派记录： 每次合并常数时间追加一条记录，总代价 $O(|E_0|)$。
• 候选分类与排序： 将剩余候选 $1$-边划分为 $\mathcal{E}_1=\{e: w(e)<w(\mathrm{kill}(e))\}$（一类边）与 $\mathcal{E}_2$（二类边），并分别按 $w(\mathrm{kill}(e))$ 降序与 $w(e)$ 升序排序。 时间 $O(|\mathcal{E}_1|\log |\mathcal{E}_1| + |\mathcal{E}_2|\log |\mathcal{E}_2|)\subseteq O(d_1\log d_1)\subseteq O(m\log m)$。

增添阶段的代价 #

增添阶段最多执行 $k-r\le d_1$ 次“加入一条 $1$-边并删一条环上最大边”的操作。

• 挑选下一条边： 由于 $\mathcal{E}_1,\mathcal{E}_2$ 事先排好序，顺序扫描即可，摊还 $O(1)$。
• 删除的环上最大边： 采用离线“指派”后，$\mathrm{kill}(e)$ 指示将被删除的那条非 $1$-边（或其等价的路径最大边），可在 $O(1)$ 时间完成替换与集合更新。

因此增添阶段总时间 $O(k-r)\le O(d_1)\le O(m)$。

总时间与空间复杂度 #

综合上述各阶段：

$$T(m,n)=O(m\log m)\quad\text{且}\quad S(m,n)=O(n+m).$$

时间的主导来自一次全局排序与 Kruskal；其余操作为线性或近线性。

可选的在线维护方案（替代“指派”） #

在某些应用中，需要动态从一棵受度或直径限制的生成树重构到另一棵，此类重新配置问题在建模与复杂度上存在额外挑战 \cite{bousquet2022reconfiguration}。

若不使用离线“指派”，可用 Link-Cut Tree（LCT）/树剖 + 线段树维护当前树上路径最大边， 则每次“加入一条 $1$-边并删除环上最大边”在 $O(\log n)$ 时间完成； 增添阶段复杂度变为 $O((k-r)\log n)$，总复杂度

$$O(m\log m + (k-r)\log n)\subseteq O(m\log m + m\log n).$$

在实际实现中，离线“指派”更简洁，常数因子更小。

与朴素/改进基线的比较 #

• 朴素枚举（仅作小规模）： 穷举 $\binom{d_1}{k}$ 种 $1$-边选择，每次做一遍 MST 检查，复杂度爆炸，仅在 $n\le 10$ 可行。
• 基于二分“最小瓶颈”的检查： 对最大边权做二分，每次用并查集验证可行性， 复杂度 $O\big(m\log m + (\log m)\cdot (m\alpha(n))\big)=\tilde O(m\log m)$，但常数较大， 且需要额外的可行性与度数达成性判断逻辑。
• 本文算法： 单次排序 + Kruskal + 离线“指派”，总体 $O(m\log m)$， 常数小、实现简洁，并且直接输出词典序最小解而非仅判定可行。

关于下界与可改进空间 #

在基于比较的模型下，对任意实权边集进行完全排序需要 $\Omega(m\log m)$ 次比较； Kruskal 亦以排序为主要瓶颈，因而 $O(m\log m)$ 是自然的上界。 若权值可做线性时间桶化/基数排序（例如整数小范围权），则整体可达 $O(m+n)$ 级别； 若采用更高阶的 MST 线性/次线性算法（例如随机化 Karger–Klein–Tarjan 框架）， 本问题亦可在相近的复杂度范围内实现，不过实现复杂度显著提高，且需要将单点度约束与词典序判定谨慎嵌入该框架。