1. 简介
在本文中，我们将介绍 Akra-Bazzi 方法。这是一种用于分析 分治算法时间复杂度 的通用数学工具。相比大家更熟悉的 Master Theorem（主定理），Akra-Bazzi 方法适用范围更广，尤其适用于子问题规模不一致的递归式。
2. 分治算法的复杂度分析
2.1 主定理回顾
主定理适用于如下形式的递归：
$$ T(n) = aT\left(\frac{n}{b}\right) + g(n) $$
其中：
- $ a \geq 1 $：子问题个数
- $ b > 1 $：每个子问题的规模是原问题的 $ \frac{1}{b} $
- $ g(n) $：合并子问题所需的额外工作量（通常是线性或线性对数）
✅ 主定理局限：它要求所有子问题大小一致。当递归式中出现不同大小的子问题时（例如 $ T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + 2n $），主定理就无能为力了。
3. Akra-Bazzi 方法详解
3.1 基本形式
Akra-Bazzi 方法适用于以下形式的递归式：
$$ T(n) = \begin{cases} \Theta(1), & n \leq n_0 \ g(n) + \sum_{i=1}^{k} a_i T(b_i n + h_i(n)), & n > n_0 \end{cases} $$
其中：
- $ a_i > 0 $：第 $ i $ 个子问题的权重
- $ 0 < b_i < 1 $：第 $ i $ 个子问题的规模比例
- $ h_i(n) \in O\left(\frac{n}{\log^2 n}\right) $：修正项，用于处理 floor/ceil 等操作
- $ g(n) $：非负函数，表示合并与分解的开销
3.2 核心公式
设 $ p $ 是以下方程的唯一实数解：
$$ \sum_{i=1}^{k} a_i b_i^p = 1 $$
则根据 Akra-Bazzi 定理，递归式的渐近复杂度为：
$$ T(n) \in \Theta\left(n^p \left(1 + \int_{1}^{n} \frac{g(u)}{u^{p+1}} du \right)\right) $$
⚠️ 注意：积分必须收敛，即：
$$ \int_{1}^{n} \frac{g(u)}{u^{p+1}} du < \infty $$
3.3 实用简化版本（多项式 $ g(n) $）
当 $ g(n) $ 是多项式函数时（如 $ g(n) = 2n $），我们可以使用以下简化规则：
设 $ g(n) \in \Theta(n^q) $，则：
$$ T(n) \in \begin{cases} \Theta(n^p), & q < p \ \Theta(n^p \log n), & q = p \ \Theta(n^q), & q > p \end{cases} $$
这个简化规则非常实用，大多数实际算法的 $ g(n) $ 都是多项式形式。
3.4 实现技巧与注意事项
- 忽略 floor/ceil：在实际应用中，我们通常忽略 $ h_i(n) $，直接使用 $ T(\frac{n}{b_i}) $，因为 floor/ceil 不影响渐近复杂度。
- 边界条件不影响渐近复杂度：递归式中的初始条件（如 $ T(1) = 1 $）不影响最终的渐近行为。
- **数值解 $ p $**：如果无法解析求解 $ p $，可以使用 牛顿迭代法 或其他数值方法近似求解。
4. 示例分析
考虑以下递归式：
$$ T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + 2n $$
4.1 求解 $ p $
根据 Akra-Bazzi 定理，我们有：
$$ a_1 = a_2 = 1, \quad b_1 = \frac{1}{2}, \quad b_2 = \frac{1}{4} $$
代入方程：
$$ \left(\frac{1}{2}\right)^p + \left(\frac{1}{4}\right)^p = 1 $$
注意到 $ \frac{1}{4} = \left(\frac{1}{2}\right)^2 $，所以：
$$ x + x^2 = 1 \quad \text{其中 } x = \left(\frac{1}{2}\right)^p $$
解得：
$$ x = \frac{1 + \sqrt{5}}{2}, \quad p = \log_{1/2} \left( \frac{1 + \sqrt{5}}{2} \right) \approx -0.694 $$
4.2 应用 Akra-Bazzi 公式
计算积分：
$$ \int_{1}^{n} \frac{2u}{u^{-0.694 + 1}} du = 2 \int_{1}^{n} u^{0.694} du = 1.181 n^{1.694} - 1.181 $$
代入公式：
$$ T(n) \in \Theta\left(n^{-0.694}(1 + 1.181 n^{1.694} - 1.181)\right) = \Theta(n) $$
4.3 使用简化规则验证
由于 $ g(n) = 2n \in \Theta(n^1) $，而 $ p \approx -0.694 < 1 $，所以根据简化规则：
$$ T(n) \in \Theta(n) $$
✅ 结论一致：两种方法都得出 $ T(n) \in \Theta(n) $，说明分析是可靠的。
5. 总结
- Akra-Bazzi 方法 是分析分治算法复杂度的强大工具。
- 它适用于主定理无法处理的递归式（如子问题大小不一致的情况）。
- 使用时需注意：
- 确保 $ g(n) $ 满足多项式增长条件
- 积分收敛
- 可以使用简化规则快速判断复杂度
- 实际应用中，忽略 floor/ceil、使用数值方法求解 $ p $ 是常见做法。
✅ 适合场景：当你遇到类似 $ T(n) = T(n/2) + T(n/4) + f(n) $ 这类递归式时，Akra-Bazzi 方法就是你的首选分析工具。