C++ Con 2024: Amortized Complexity

《C++ Con 2024: Amortized Complexity》讲解了分摊复杂度（Amortized Complexity）的概念及其分析方法，重点阐述了如何通过分摊复杂度来评估算法的性能。以下是总结： ### 分摊复杂度的定义 分摊复杂度是对一系列操作的总代价进行平均，以反映单个操作的平均代价。它适用于那些单次操作代价波动较大的场景。 ### 常见的复杂度分析方法 1. **聚合分析法** - 将一系列操作的总代价视为与输入规模呈线性关系的函数。 - **案例**：假设某操作的代价为 `ci`，其中 `c1 = O(s)`，`ci > 1 时 c_i = O(1)`，则总代价 `T(n) = O(n + s)`。分摊后每次操作的代价为 `O(1)`。 2. **势能法（Potential Method）** - 通过引入势能函数 `Φ`，将实际代价 `ci` 分配到一系列操作中。 - **案例**：假设 `Φi` 表示第 `i` 次操作后的势能，初始势能 `Φ0 = 0`，则分摊代价为 `ˆci = ci + Φi - Φ(i-1)`。若 `ˆci ∈ O(1)`，则总代价的分摊复杂度为线性。 ### 示例分析 1. **对 `filter view::begin()` 的分析** - 第一个操作代价为 `O(s)`，后续操作代价为 `O(1)`。 - 使用聚合分析法，总代价 `T(n) = O(n + s)`，分摊后每次操作为 `O(1)`。 - 使用势能法时，发现初次操作的势能可能为负值，违反势能函数的定义，因此需要重新校准势能分配。 2. **对 `v.push_back(3)` 的分析** - 该操作通常被认为是 `O(1)` 分摊复杂度，但传统复杂度分析可能认为其为 `O(s)`，具体取决于上下文和实现细节。 ### 结论 分摊复杂度通过平均一系列操作的总代价，提供了更贴近实际场景的性能评估。聚合分析法和势能法是两种常用的分摊复杂度分析方法，具体选择方法需根据问题特点灵活应用。