关于主定理的一个简洁的证明

TLE_Automat · 2025-04-27 17:04:00 · 算法·理论

关于主定理的一个简洁的证明

前言

上个赛季某次在 1121 训练时吐槽主定理难证，被翔哥听到骂了一顿，然后他给我讲了一种跟网上主流的证明方法非常不同的方法，仅用到高中学的简单的数列递推和归纳法，令我耳目一新，不过当时一带而过了，并没有记录下来。

直到今天的算法设计与分析课上重新提到了主定理，我再次从网上搜索证明，还是只能搜到那些长篇大论的推导，于是我重新回忆了一下翔哥教给我的推导方法，并打算开个博客记录一下。

定理

主定理适用于求解如下递归式算法的时间复杂度

结论为

证明

令 n = b^{k}（如果无法取整，则可以找到最小的 k 使得 b^{k} > n，根据后续结论，这样做对时间复杂度只会产生常数级别的影响），则递归式可写为

• 先来分析 b^{d} = a 时的情况，此时递归式可写为

  \begin{aligned} T(b^{k}) = aT(b^{k - 1}) + O(a^{k}) \end{aligned}

  将式子两边同时除以 a^{k}​，可得

  \begin{aligned} \frac{T(b^{k})}{a^{k}} = \frac{T(b^{k - 1})}{a^{k - 1}} + O(1) \end{aligned}

  不难发现

  \frac{T(b^{k})}{a^{k}} = O(k)

  即

  \begin{aligned} T(n) = T(b^{k}) = O(a^{k}k) = O(b^{kd}k) = O(n^{d}\log n) \end{aligned}

• 当 b^{d} > a​ 时，考虑归纳法。

  显然，当 k = 0 时，T(b^{k}) = T(1) = O(1) = O(b^{kd}) 成立。

  假设 T(b^{k}) = O(b^{kd}) 在 k \le K 时成立。

  考虑在 k = K + 1 时，带入递归式得

  \begin{aligned} T(b^{K + 1}) = aT(b^{K}) + O(b^{(K + 1)d}) = O(ab^{Kd} + b^{(K + 1)d}) \end{aligned}

  由于 b^{d} > a，所以 ab^{Kd} < b^{d}b^{Kd} = b^{(K + 1)d}，故

  \begin{aligned} T(b^{K + 1}) = aT(b^{K}) + O(b^{(K + 1)d}) = O(b^{(K + 1)d}) \end{aligned}

  即 T(b^{k}) = O(b^{kd}) 在 k = K + 1 时也成立，故

  T(n) = T(b^{k}) = O(b^{k}d) = O(n^{d})

• 当 b^{d} < a 时，同理，也考虑归纳法。

  显然，当 k = 0 时，T(b^{k}) = T(1) = O(1) = O(a^{k})​ 成立。

  假设 T(b^{k}) = O(a^{k}) 在 k \le K 时成立。

  考虑在 k = K + 1​ 时，带入递归式得

  \begin{aligned} T(b^{K + 1}) = aT(b^{K}) + O(b^{(K + 1)d}) = O(a^{K + 1} + b^{(K + 1)d}) \end{aligned}

  由于 b^{d} < a，所以 a^{K + 1} > (b^{d})^{K + 1} = b^{(K + 1)d}，故

  \begin{aligned} T(b^{K + 1}) = aT(b^{K}) + O(b^{(K + 1)d}) = O(a^{K + 1}) \end{aligned}

  即 T(b^{k}) = O(a^{k}) 在 k = K + 1​ 时也成立，故

  T(n) = T(a^{k}) = O(b^{k(\log_{b}{a})}) = O(n^{\log_{b}a})