渐近复杂度、归约与可计算性

问题族、编码与输入规模

复杂度描述随输入增长的一族实例，不是一次运行的秒数。先规定问题、输入编码和计算模型。若实例编码为字符串 $x$，最常用规模是 $n=|x|$，即符号数或位数。运行时间 $T_A(x)$ 可计基本操作，空间计同时存活的工作存储；不同合理模型之间通常允许多项式模拟，但具体常数和低阶项仍影响工程性能。

数值 $N$ 的二进制编码只需 $n=\lfloor\log_2N\rfloor+1$ 位。因此执行 $N$ 次循环的算法对数值大小是 $O(N)$，对位长度却是 $O(2^n)$。称某算法“多项式”前必须说明相对于哪个编码长度。若输入是图，可取 $n=|V|+|E|$ 或明确的邻接矩阵位数；若输出本身很大，还应给输出敏感复杂度。

最坏、平均与摊还不是三个同义平均

固定长度 $n$ 的最坏时间为

给所有该规模输入的保证。最好情况通常只说明某些输入容易，不能代表稳健上界。平均时间必须给每个规模上的分布 $D_n$：

没有分布就没有唯一“平均情况”；均匀分布也未必存在或符合真实数据。随机算法还要区分对固定输入取算法随机性的期望，和同时对输入分布取期望。

摊还分析不假设随机分布。它对任意操作序列证明总成本上界，再除以操作数。某一次操作仍可能昂贵，但连续大量操作的平均由结构不变量保证。聚合法直接求总和，记账法给便宜操作预存信用，势能法选择非负势函数 $\Phi$，定义摊还成本

求和后势能差望远镜消去。势函数需有明确初值和下界，不能为得到答案随意指定负信用。

O、Ω、Θ 的量词顺序

对最终非负函数，

表示存在常数 $c>0,n_0$，使所有 $n\ge n_0$ 都有 $f(n)\le cg(n)$。相应地，$f\in\Omega(g)$ 表示最终有 $f(n)\ge cg(n)$；$f\in\Theta(g)$ 表示同时属于两者。常数必须独立于 $n$，而 $n_0$ 允许忽略有限前缀。

$O$ 是上界集合，不表示紧确相等。$n^2\in O(n^3)$ 虽然正确，却不精确；若已知上下界同阶才写 $\Theta(n^2)$。算法的 $O(n^2)$ 上界与问题的 $\Omega(n\log n)$ 下界可以同时成立，中间差距表示分析或算法仍可能改进。对数底数只差常数，但指数底数不能忽略。

复杂度还需注明资源和参数。递归算法可能时间理想却用过深调用栈；位运算模型与单位成本 RAM 对大整数乘法计价不同；参数化算法写成 $f(k)n^{O(1)}$ 时，困难性集中在参数 $k$。同一个问题可有精确、近似、随机或特殊图类算法，它们的保证不能只用一个 $O$ 符号比较。

比较排序下界来自决策树

只允许比较两个键、输入键互异的确定性排序，可表示为二叉决策树。每个内部节点是一项比较，每个叶子必须区分一种输入排列。共有 $n!$ 种排列，所以树至少有 $n!$ 个叶子；高度 $h$ 的二叉树最多 $2^h$ 个叶子，故

这给最坏比较次数下界。归并排序等算法达到 $O(n\log n)$，因此在比较模型中渐近最优。计数排序、基数排序使用键范围或数字位结构，不只做比较，所以不与该下界矛盾。随机比较排序的期望下界还需相应概率论证，不能从确定性树一句话直接覆盖所有模型。

判定、可识别与停止保证

为讨论可计算性，把判定问题表示为语言 $L\subseteq\Sigma^*$。判定器对每个输入都停止，并在 $x\in L$ 时接受、$x\notin L$ 时拒绝。识别器或半判定器只保证成员最终被接受；对非成员可以拒绝，也可以永远运行。运行超时不是数学上的拒绝，除非算法已经证明该时间界足以完成。

若 $L$ 与补语言 $\overline L$ 都可识别，可交错运行两个识别器，其中一个最终接受，从而判定 $L$。可判定必然可识别，但反向不成立。工程上的“还没找到答案”可能是实例很难、实现很慢或算法根本不保证停止，三者要分别陈述。

不可判定表示不存在对所有合法输入都正确停止的算法，不表示每个实例都无法回答。停机分析可以正确处理许多受限程序；被排除的是覆盖任意程序和输入的万能判定器。

映射归约的方向决定结论

语言 $A$ 多对一映射归约到 $B$，记为 $A\le_m B$，若存在可计算函数 $f$，满足

于是若能判定 $B$，先算 $f(x)$ 再调用 $B$ 判定器即可判定 $A$。因此为证明 $B$ 至少和已知困难问题 $A$ 一样难，应从 $A$ 归约到 $B$；反向只说明 $A$ 能帮助解 $B$，不能推出 $B$ 困难。复杂度理论中的多项式时间归约还要求 $f$ 在输入长度的多项式时间内计算，并产生多项式长度输出。

P、NP 与“困难”的准确含义

P 是可由确定性算法在输入长度多项式时间内判定的语言类。NP 是存在多项式长度证书，并可由确定性多项式时间验证器验证“是”实例的语言类；等价地，可由非确定性 Turing 机多项式时间判定。显然 $\mathrm P\subseteq\mathrm{NP}$，而是否 $\mathrm P=\mathrm{NP}$ 仍未知。

NP 绝不表示“非多项式”。很多 P 问题也属于 NP；对一般 NP 问题，只是尚不能由定义保证有已知确定性多项式算法。若所有 NP 问题都能多项式归约到 $B$，称 $B$ 为 NP-hard；若 $B$ 同时属于 NP，则为 NP-complete。NP-hard 问题可以不是判定问题，甚至可以不可判定，因此必须分别证明“属于 NP”和“足够困难”。

优化问题常先关联一个阈值判定版本。找到最优解、验证候选解和判断是否存在不超过阈值的解是不同任务。指数上界只说明有算法，不能证明不存在更快算法；NP-hard 也不等于每个实例都难，特殊结构、参数化或近似算法可能实用。

先判断结论属于哪一层

面对一个新问题，应把“有没有算法”“需要多少资源”和“当前是否已有实现”分开。证明一个语言可判定，只需给出总会停止的正确算法；即使该算法耗时极大，也已经越过可计算性边界。给出多项式、指数或更高的时间界是在可判定之后讨论资源上界。下界则必须注明模型与归约假设：比较模型中的排序下界不能自动推广到整数 RAM，条件性的 NP-hard 结论也不等于无条件时间下界。

反过来，尚未找到快速算法只是知识状态，不是数学证明。若某问题有 $O(2^n)$ 枚举算法，我们知道它可判定并有指数上界，却不能据此断言最优复杂度就是指数级；若它被证明 NP-complete，我们得到的是在通常多项式归约框架下的困难性，而且“除非 P=NP，不存在多项式算法”仍带公开假设。若问题不可判定，则任何对全部输入承诺正确停止的实现都不可能存在，但受限输入、保守分析器或允许返回“未知”的半算法仍有价值。

因此报告结论时应写完整证据链：算法给上界，决策树或其他论证给无条件下界，归约把已知困难性传递到目标问题，对角构造否定万能判定器。把这些证据放在同一张“层级表”里，才能避免用工程超时冒充不可判定，也避免用某个慢实现冒充问题下界。

停机问题的对角论证轮廓

假设存在程序 $H(P,x)$，对任意程序编码 $P$ 和输入 $x$ 都停止，并正确回答 $P(x)$ 是否停止。构造程序 $D(P)$：先运行 $H(P,P)$；若回答“会停止”，$D$ 就进入无限循环；若回答“不会停止”，$D$ 立即停止。

现在运行 $D(D)$。若 $H(D,D)$ 回答会停止，按定义 $D(D)$ 不停止；若回答不停止，按定义 $D(D)$ 反而停止。两种都与 $H$ 的正确性矛盾，所以万能停机判定器不存在。

论证依赖程序可编码并把自身编码作为输入，不是因为机器内存有限或等待时间不够。它证明根本不可判定；与 P 对 NP 的资源问题不同，后者讨论已经可判定问题能否在多项式时间解决。把超时、指数时间、NP-complete 和不可判定统称“算不出来”，会丢失最重要的边界。

交互实验：从操作轨迹辨认增长阶

先选择算法族和输入规模，预测关键操作计数是常数、对数、线性、线性对数还是平方增长。实验逐步显示控制流轨迹，同时保存精确的比较、交换或访问次数；改变输入排列时，可分别观察最好、最坏与给定样本的实际轨迹，而不是把一次运行时间直接当作渐近复杂度。

点击播放或单步后，比较相邻规模的计数比和对数坐标斜率，并保持算法、成本模型和输入生成规则不变。计时会受解释器、缓存和系统负载影响，操作计数也依赖选定模型；两者都不能证明不可判定或 NP-hard。分享链接应保存算法、输入、规模、种子和当前步骤，便于复现同一轨迹。

练习

关系与资源

• 动态规划与图算法
• 证明策略与反例
• 逻辑、量词与证明语言
• 数据结构与算法综合复习

MIT OpenCourseWare 6.006 用于核对渐近分析、摊还成本、排序下界和算法证明口径。可计算性与 P/NP 部分只给定义和论证轮廓，不把开放问题写成定论。

MIT《Mathematics for Computer Science》为本章的可计算性论证提供离散数学基础：可数性与对角化用于说明“问题可描述”不等于“存在终止算法”，命题逻辑和归约语言用于区分判定问题、验证过程与复杂度类别。由此，本章关于不可判定性和 P、NP 的陈述被限制在已证明结论内，不把尚未解决的类别关系当作事实。