JIANGEPLUS 正确性与复杂度
功能定位
为算法方案提供"凭什么对"和"代价是多少"的严谨账本。可独立调用，也可由 algorithm-engineer 总纲路由而来。
触发条件
TRIGGER：证明正确性 / 为什么对 / 复杂度多少 / 最坏·均摊·期望 / 空间复杂度 / 是否全局最优 / 近似比与概率保证 / 伪多项式判定 / 递归栈与复制开销核算。
DO NOT TRIGGER：
- 尚未选定算法、需要方向 →
algorithm-modeling - 需要实测跑分与 profiler →
algorithm-implementation - 图/字符串/几何/数论的领域前提 →
algorithm-domain-checks
工作流程
- 明确要证明什么：终止性、最优性、覆盖性、等价性还是保证边界。
- 按算法类型选择证明义务（见下表）并逐条落实。
- 无法证明的部分显式列出，并尝试构造反例。
- 建立复杂度账本：定义输入参数与计算模型 → 分别统计预处理、单次操作、总操作数、输出大小。
- 区分最坏 / 均摊 / 期望，注明随机性或分布假设。
- 输出保证范围：精确解 / 近似保证 / 概率保证 / 局部最优 / 启发式。
证明义务清单
| 类型 | 必须说明 |
|---|---|
| 循环 | 初始化成立 → 每轮保持 → 终止时得到要求，并说明为何终止 |
| DP | 状态语义、基本情形、合法且完整的转移、计算顺序、最终答案位置；空间压缩检查是否覆盖仍需使用的旧值 |
| 贪心 | 局部选择可扩展为最优的论证（如交换论证），不得以"直觉最划算"代替 |
| 搜索 | 状态覆盖完整、剪枝不删除所需解、处理重复状态与环 |
| 归约 | 映射方向、构造代价、解的可转换性；无法证明归约就不宣称难度等价 |
| 近似/随机 | 适用条件、保证定义、失败概率或"未有保证"；单次实验不是概率证明 |
复杂度账本要求
- 定义
n、m、k等参数与计算模型，分别统计预处理 / 单次操作 / 总操作数 / 输出大小。 - 最坏、均摊、期望不是同义词；均摊不是"随机平均"。
- 辅助空间与输入/输出空间分开；递归栈、对象开销、复制与缓存不能漏算。
- 整数数值范围也是约束；以容量值为维度的 DP 需检查其与编码位长的关系（伪多项式）。
- 渐近符号不能说明墙钟时间：常数、局部性、语言对象、I/O、并发与数据分布可能主导工程表现。
- 不宣称某固定规模必能一秒通过，除非在同一评测环境实测。
约束与注意事项
- 不用强行制造形式证明；不确定部分显式列出并尝试反例。
- 测试通过不能替代证明；未证明就不声称全局最优。
- 证明内容必须与实际代码的条件、更新顺序一致。
输出格式
- 结论与适用前提
- 正确性依据（分条，标明类型）与未证明部分
- 复杂度账本（参数定义、时间、空间、假设）
- 保证范围（精确 / 近似 / 概率 / 启发式）与残留风险
- 审查场景可用总纲的
templates/solution-review.md
参考文档
| 文档 | 用途 |
|---|---|
| references/proof-and-complexity.md | 证明义务与复杂度账本细则 |