使用主定理求解递归式

主定理是分治算法分析中非常重要的定理。

如，我们要处理一个 规模为 \(n\) 的问题通过分治，得到 \(a\) 个规模为 \(\dfrac{n}{b}\) 的问题，分解子问题和合并子问题的时间是 \(f(n)\)：\(T(n) = aT(\frac{n}{b})+f(n)\)。

在上面这个式子里，我们得要求 \(a \geqslant 1, b> 1\)（如果 \(b=1\) 时，递推无意义），\(f(n)\) 是渐进意义上的正数。

回顾一下，\(a\) 和 \(b\) 的含义：

• \(a\) 个子问题，即 \(a\) 是原问题分为子问题的个数；
• 每个子问题的规模是 \(\dfrac{n}{b}\)；
• 分治算法共三部分，分治合，而 \(f(n)\) 就是分 + 合的时间。\(\left \lfloor \frac{n}{b} \right \rfloor\) 和 \(\left \lceil \frac{n}{b} \right \rceil\) ，向下取整和向上取整的细节，并不会影响主定理的推导，具体的数学证明，略。

而后呢，根据上面的式子我们会得到三种情况：

• 若有实数大于零 \((\varepsilon >0),f(n)=O(n^{\log_{b}a-\varepsilon})\)，则 \(T(n)=\Theta (n^{\log_{b}a})\)；
• 若 \(f(n)=\Theta (n^{\log_{b}a})\)，则 \(T(n)=\Theta (n^{\log_{b}a}\log_n)\)；
• 若有实数大于零 (\(\varepsilon >0)\)\(f(n)=\Omega (n^{\log_{b}a+\varepsilon })\)，使得较大的 \(n\)，满足 \(af(\frac{n}{b})\leqslant cf(n)\)，这时候则 \(T(n) = \Theta (f(n))\)。

这三种情况看起来很复杂，搞清楚他们之间的关系，快速记忆就简单了。

对于三种情况的每一种，我们将函数 \(f(n)\) 与 \(n^{\log_{b}a}\) 比较，俩个函数较大者将决定递归式的解。

• 若函数 \(n^{\log_{b}a}\) 更大，如情况 \(1\)，则解是 \(T(n)=\Theta (n^{log_{b}a})\)；注意 \(f(n)\) 小于 \(n^{\log_{b}a}\) 是渐进意义上的，要差一个因子量级 \(n^{\varepsilon }(\varepsilon >0)\)。

• 若函数 \(f(n)\) 更大，如情况 \(3\)，则解是 \(T(n) = \Theta (f(n))\)；注意 \(f(n)\) 大于 \(n^{\log_{b}a}\) 是渐进意义上的，要差一个因子量级 \(n^{\varepsilon }(\varepsilon >0)\)，还要满足 \(af(\frac{n}{b})\leqslant cf(n)\)；

• 若俩个函数相等，如情况 \(2\)，则乘上一个对数因子，解为 \(T(n)=\Theta (n^{\log_{b}a}~\log_n)\)；

• 上面的三种情况并未覆盖 \(f(n)\) 的所有可能性，情况 \(1\)、情况 \(2\) 之间存在间隙，\(f(n)\) 可能小于 \(n^{\log_{b}a}\) 但不是多项式意义上的小于；情况 \(2\)、情况 \(3\) 之间也存在间隙，\(f(n)\) 可能大于\(n^{log_{b}a}\) 但不是多项式意义上的大于；若函数 \(f(n)\) 在这俩个间隙中，或者是情况 \(3\) 中要求的 \(af(\frac{n}{b})\leqslant cf(n)\) 条件不成立，就不能使用主方法来解决递归式。

首先，得明白一个基准函数：\(\Theta (n^{log_{b}a})\)。

有了基础函数之后，就可以根据 TA 来判定情形之间的关系。

那我们该如何记忆这个基准函数呢 ？？

原来的函数是：\(aT(\frac{n}{b})+f(n)\) 为底数，如果化为对数形式也是以 \(b\) 为底 \((\log_{b}a)\)；

原函数是一个多项式，\(a\) 和 \(b\) 都是常数，算出来肯定也是一个具体的数值。

所以，我们要记这样一个基准多项式（基准函数）：\(\Theta (n^{?})\)，次方（即 \(?\)）是取对数的。

接下来，是以上三种情况的判定：

• \(f(n)\) 是弱于基准的，\(O(n^{\log_{b}a-\varepsilon })<\Theta (n^{\log_{b}a})\)；
• \(f(n)\) 是等于基准的，\(\Theta (n^{\log_{b}a})=\Theta (n^{\log_{b}a})\)；
• \(f(n)\) 是强于基准的，\(\Omega (n^{\log_{b}a+\varepsilon })>\Theta (n^{\log_{b}a})\)。

例子

算例 \(1\)：\(T(n)=4T(\frac{n}{4})+\Theta (1)\)（乐高铺积木）

分析，\(a = b =4\)，基准函数是 \(\Theta (n^{\log_{4}4})\)，因为 \(\log_{4}4=1\)，所以基准函数是 \(\Theta (n)\)。

又因为 \(f(n) = \Theta (1)\) 比基准函数 \(\Theta (n)\) 要弱，我们取一个实数 \((\varepsilon=1)\)，即 \(\Theta (1)=O(n^{1-\frac{1}{2}}) = O(\sqrt{n})\)。

得到 \(T(n)=\Theta (n )\)。

算例 \(2\)：\(T(n)=T(\frac{n}{2})+\Theta (1)\)（二分查找）

分析，\(a = 1, b=2\)，基准函数是 \(\Theta (n^{log_{2}1})\)，因为 \(\log_{2}1=0\)，所以基准函数是 \(\Theta (1)\)。

又因为 \(f(n)=\Theta(1)\)，基准函数也是 \(\Theta(1)\) ，\(f(n)\) = 基准函数，再乘上一个 \(\log n\)，即 \(T(n)=\Theta(\log n)\)。

算例3：\(T(n)=2T(\dfrac{n}{2})+\Theta(n)\) （归并排序）

分析，\(a=b=2\)，基准函数是 \(\Theta (n^{\log_{2}2})\)，因为 \(\log_{2}2=1\)，所以基准函数是 \(\Theta (n)\)。

又因为 \(f(n)=\Theta (n)\)，基准函数也是 \(\Theta (n)\)，\(f(n)=\) 基准函数，最后 \(T(n)=\Theta (n~logn)\)。

摘自 主定理 士 - CSDN博客_主定理。