# Algorithm Proof

> 算法正确性与复杂度核算：循环不变式、DP 状态语义、贪心交换论证、搜索覆盖、归约、近似与随机保证，以及完整复杂度账本。TRIGGER —— 证明正确性、为什么对、复杂度多少、最坏/均摊/期望、空间复杂度、是否最优、近似保证、伪多项式。DO NOT TRIGGER —— 算法选型（→ algorithm-modeling）、跑分与测量（→ algorithm-implementation）、领域前提核查（→ algorithm-domain-checks）。

- Skill: `jiangeplus/algorithm-proof` (Agent Skill, multi-file: 4 files)
- Install (CLI): `npx skillmds@latest add jiangeplus/algorithm-proof`
- Raw SKILL.md: https://api.skillmd.com/api/skills/jiangeplus/algorithm-proof/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- License: MIT
- Author: JIANGEPLUS (https://skillmd.com/u/jiangeplus)
- Updated: 2026-09-22
- Page: https://skillmd.com/skills/jiangeplus/algorithm-proof

---


# 正确性与复杂度

## 功能定位

为算法方案提供"凭什么对"和"代价是多少"的严谨账本。可独立调用，也可由 `algorithm-engineer` 总纲路由而来。

## 触发条件

**TRIGGER**：证明正确性 / 为什么对 / 复杂度多少 / 最坏·均摊·期望 / 空间复杂度 / 是否全局最优 / 近似比与概率保证 / 伪多项式判定 / 递归栈与复制开销核算。

**DO NOT TRIGGER**：
- 尚未选定算法、需要方向 → `algorithm-modeling`
- 需要实测跑分与 profiler → `algorithm-implementation`
- 图/字符串/几何/数论的领域前提 → `algorithm-domain-checks`

## 工作流程

1. 明确要证明什么：终止性、最优性、覆盖性、等价性还是保证边界。
2. 按算法类型选择证明义务（见下表）并逐条落实。
3. 无法证明的部分显式列出，并尝试构造反例。
4. 建立复杂度账本：定义输入参数与计算模型 → 分别统计预处理、单次操作、总操作数、输出大小。
5. 区分最坏 / 均摊 / 期望，注明随机性或分布假设。
6. 输出保证范围：精确解 / 近似保证 / 概率保证 / 局部最优 / 启发式。

## 证明义务清单

| 类型 | 必须说明 |
|------|---------|
| 循环 | 初始化成立 → 每轮保持 → 终止时得到要求，并说明为何终止 |
| DP | 状态语义、基本情形、合法且完整的转移、计算顺序、最终答案位置；空间压缩检查是否覆盖仍需使用的旧值 |
| 贪心 | 局部选择可扩展为最优的论证（如交换论证），不得以"直觉最划算"代替 |
| 搜索 | 状态覆盖完整、剪枝不删除所需解、处理重复状态与环 |
| 归约 | 映射方向、构造代价、解的可转换性；无法证明归约就不宣称难度等价 |
| 近似/随机 | 适用条件、保证定义、失败概率或"未有保证"；单次实验不是概率证明 |

## 复杂度账本要求

- 定义 `n`、`m`、`k` 等参数与计算模型，分别统计预处理 / 单次操作 / 总操作数 / 输出大小。
- 最坏、均摊、期望不是同义词；均摊不是"随机平均"。
- 辅助空间与输入/输出空间分开；递归栈、对象开销、复制与缓存不能漏算。
- 整数数值范围也是约束；以容量值为维度的 DP 需检查其与编码位长的关系（伪多项式）。
- 渐近符号不能说明墙钟时间：常数、局部性、语言对象、I/O、并发与数据分布可能主导工程表现。
- 不宣称某固定规模必能一秒通过，除非在同一评测环境实测。

## 约束与注意事项

- 不用强行制造形式证明；不确定部分显式列出并尝试反例。
- 测试通过不能替代证明；未证明就不声称全局最优。
- 证明内容必须与实际代码的条件、更新顺序一致。

## 输出格式

- 结论与适用前提
- 正确性依据（分条，标明类型）与**未证明部分**
- 复杂度账本（参数定义、时间、空间、假设）
- 保证范围（精确 / 近似 / 概率 / 启发式）与残留风险
- 审查场景可用总纲的 `templates/solution-review.md`

## 参考文档

| 文档 | 用途 |
|------|------|
| [references/proof-and-complexity.md](references/proof-and-complexity.md) | 证明义务与复杂度账本细则 |