算法与数据结构
一、算法的本质模型（第一性原理）
算法不是代码，而是一种受约束的"问题求解规则体系"。
从第一性原理看，算法可以被抽象为四个不可分割的要素：
算法 = 问题建模 + 状态与转移规则 + 正确性约束 + 资源约束
| 维度 | 核心问题 | 对应关注点 |
|---|---|---|
| 问题建模 | 要解决的是什么问题 | 输入、输出、约束条件 |
| 状态与转移 | 如何从初始状态到目标状态 | 控制流程、递归 / 迭代 |
| 正确性约束 | 是否对所有合法输入成立 | 不变式、数学证明 |
| 资源约束 | 是否可在现实系统中运行 | 时间 / 空间复杂度 |
该模型贯穿全文，是后续所有分析的统一认知锚点。
二、算法的基本属性（公理层）
算法作为一种形式化求解过程，必须满足以下必要条件：
- 有穷性：算法在有限步骤内终止
- 确定性：每一步操作含义明确、无歧义
- 可行性：每个操作在物理或抽象机器上可执行
- 输入 / 输出：问题定义清晰，结果可被观测
这些属性不是"好算法"的标准，而是算法存在的前提条件。
三、算法评价的分层体系（从理论到工程）
算法的评价标准并不处于同一层级，应当进行结构化区分。
3.1 一阶标准：正确性（不可妥协）
正确性是算法存在的前提，而非优化目标。
循环不变式（正确性证明的核心工具）
循环不变式用于证明算法在整个执行过程中始终保持某个关键性质，其证明包含三步：
- 初始化：第一次迭代前不变式成立
- 保持性：若迭代前成立，则迭代后仍成立
- 终止性：算法结束时，不变式推出问题结论
循环不变式的本质，是用数学归纳法证明"状态转移规则"的可靠性。
3.2 二阶标准：资源约束（理论可扩展性）
当正确性成立后，算法是否"可用"，取决于其资源消耗是否可控。
时间复杂度（增长阶而非具体时间）
时间复杂度关注的是：
当问题规模趋近无穷时，算法的资源增长趋势
常见增长阶：
| 类别 | 示例 |
|---|---|
| 常数 | O(1) |
| 对数 | O(log n) |
| 线性 | O(n) |
| 多项式 | O(n²)、O(n³) |
| 指数 / 阶乘 | O(2ⁿ)、O(n!) |
多项式时间是算法工程可扩展性的理论分界线。
P / NP 的正确理解（概念澄清）
- P：存在确定性多项式时间算法的问题集合
- NP：解可以在多项式时间内被验证的问题集合
NP 是问题分类，而非算法复杂度描述
"当前最优算法是指数级" ≠ "问题属于 NP"。
不同时间复杂度视角
- 最好情况：最理想输入下的性能
- 最坏情况：保证上界（工程设计常用）
- 平均情况：依赖输入概率分布
- 均摊复杂度：长期操作序列的平均代价
均摊分析的本质是：
用时间换稳定性，避免对偶发高成本操作的误判。
递归树（分治算法分析模型）
对于分治算法，可将递归过程抽象为一棵树：
- 树高：递归深度
- 每层代价：该层所有子问题的总代价
总复杂度 ≈ 树高 × 每层总代价
该模型是主定理的直观基础。
3.3 三阶标准：工程属性（可维护性）
在理论可行的前提下，工程实践还需关注：
- 易读性：是否利于理解与协作
- 健壮性：是否能应对异常输入
- 可测试性：是否易于验证与回归
这些指标不会改变算法阶数，但决定其工程寿命。
四、算法分析的方法论总览
| 方法 | 适用场景 | 核心思想 |
|---|---|---|
| 顺序分析 | 简单流程 | 取最大增长阶 |
| 嵌套分析 | 多重循环 | 复杂度相乘 |
| 递归树 | 分治算法 | 分层求和 |
| 主定理 | 规范递归 | 数学归纳 |
| 均摊分析 | 动态结构 | 长期平均 |
这些方法本质上都是在回答同一个问题：
规模增长时，系统是否还能继续工作？
五、算法、数据结构与系统设计的关系
算法从不孤立存在，其工程价值取决于与数据结构和系统约束的匹配。
| 算法复杂度 | 工程含义 |
|---|---|
| O(n²) | 仅适合小规模、内存内计算 |
| O(n log n) | 通用高效算法上限 |
| O(log n) | 高并发索引与搜索基础 |
| 均摊 O(1) | 哈希表、缓存、队列核心特性 |
算法复杂度决定系统的规模上限，数据结构决定常数项与实现路径。
六、总结：从算法知识到算法决策
- 能判断某个问题是否值得用算法解决
- 能预估系统在规模扩展时的失效点
- 能在正确性、性能与工程成本之间做理性取舍