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

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

前言

定理

证明

• 先来分析 $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^{kd}) = 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})$$