例题

使用主定理

主定理是一个强大的工具，用于解决递归关系式，通常用于分析某些递归算法的时间复杂度。当递归关系式具有以下形式时：

其中$( a \geq 1 )$和$b > 1$是常数，$f(n)$是一个已给出的函数，可以应用主定理。这个递归关系式表明，一个大小为$n$的问题的解可以通过递归地解决$a$个大小为$\frac{n}{b}$的子问题来获得，附加上$f(n)$的成本。

主定理提供了三种情况来确定$T(n)$的渐进界限：

1. 如果$f(n) = O(n^{\log_b a - \epsilon})$对于某个常数$\epsilon > 0$，那么$T(n) = \Theta(n^{\log_b a})$。
2. 如果$f(n) = \Theta(n^{\log_b a})$，那么$T(n) = \Theta(n^{\log_b a} \log n)$。
3. 如果$f(n) = \Omega(n^{\log_b a + \epsilon})$对于某个常数$\epsilon > 0$，并且对于某个常数$c < 1$且所有足够大的$n$，都有$af\left(\frac{n}{b}\right) \leq cf(n)$，那么$T(n) = \Theta(f(n))$。

在图片中提供的示例中：

• 示例 1： $T(n) = 9T\left(\frac{n}{3}\right) + n$ 这里，$a=9, b=3, f(n) = n$，因为$f(n)$符合情况 1，我们有$T(n) = \Theta(n^2)$。

• 示例 2： $T(n) = 2T\left(\frac{n}{2}\right) + 1$ 这里，$a=2, b=2, f(n) = 1$，$f(n)$符合情况 2，因此$T(n) = \Theta(\log n)$。

• 示例 3： $T(n) = 3T\left(\frac{n}{4}\right) + n \log n$ 这里，$a=3, b=4, f(n) = n \log n$，$f(n)$符合情况 3，所以$T(n) = \Theta(n \log n)$。

在应用主定理时，关键是要准确识别$f(n)$并确定其与$n^{\log_b a}$的关系。一旦确定了这种关系，就可以直接应用相应的情况来找到$T(n)$的渐进界限。

理解如何选择使用主定理的哪一种情况

说选择使用主定理的哪一种情况仅仅取决于$a$和$b$与 1 的比较是不完全准确的。相反，这个决策是基于$f(n)$与$n^{\log_b a}$之间的关系。你可以通过比较$f(n)$和$n^{\log_b a}$的增长速度来决定应用哪一种情况：

• 情况 1： 如果$f(n)$的增长速度慢于$n^{\log_b a}$，即$f(n) = O(n^{\log_b a - \epsilon})$对于某个$\epsilon > 0$，那么应用主定理的情况 1。
• 情况 2： 如果$f(n)$的增长速度与$n^{\log_b a}$相同，即$f(n) = \Theta(n^{\log_b a})$，那么情况 2 适用。
• 情况 3： 如果$f(n)$的增长速度快于$n^{\log_b a}$，即$f(n) = \Omega(n^{\log_b a + \epsilon})$对于某个$\epsilon > 0$，并且满足常数$c < 1$的正则条件$af(\frac{n}{b}) \leq cf(n)$对所有足够大的$n$，那么情况 3 适用。

记住，主定理是解决以下形式递归关系式的工具：

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

其中$a \geq 1$和$b > 1$是常数，$f(n)$是一个已给出的函数。定理帮助确定$T(n)$的渐进行为，基于非递归部分$f(n)$的增长率与$n^{\log_b a}$的比较。

• 有b个子问题，子问题规模是c，但是b和c和n没有关系，应该当成任意给的一个常数。

主定理的适用性分析

给定递归关系式： T(n) = 2T(n/2) + n log n 我们需要分析是否可以应用主定理来求解。主定理适用于以下形式的递归关系式：

其中 $a ≥ 1$ 和 $b > 1$ 是常数，$f(n)$ 是与 $n$ 相关的函数。

对于我们的递归关系式：

• $a = 2$，表示递归解决每个子问题的数目。
• $b = 2$，表示每个子问题的大小是原问题大小的一半。
• $f(n) = n log n$，表示在递归之外需要进行的计算。

主定理要求比较 $f(n)$ 与 $n^{\log_b a}$ 的增长速率。在这个例子中，$n^{\log_b a}$ 等于 $n$。因为 $f(n)$，即 $n log n$，增长速度比 $n$ 快，它不符合主定理第一种或第二种情况的要求。

对于主定理的第三种情况，$f(n)$ 必须是 $\Omega(n^{\log_b a + \epsilon})$，对某个正常数 $\epsilon > 0$。虽然 $n log n$ 增长确实比 $n$ 快，但它不符合 $n^{1+\epsilon}$ 的形式，因此不满足第三种情况的 $\Omega(n^{\log_b a + \epsilon})$ 条件。

结论

因此，我们无法直接使用主定理来求解给定的递归关系式，原因如下：

• $f(n)$ 不是多项式级别低于 $n$，因此不满足主定理的第一种情况。
• $f(n)$ 也不与 $n$ 增长速率相同，因此不满足主定理的第二种情况。
• $f(n)$ 不满足 $\Omega(n^{\log_b a + \epsilon})$ 形式，因此不满足主定理的第三种情况。

这意味着我们需要寻找其他方法来分析此递归关系式的时间复杂度，比如使用递归树或者Akra-Bazzi 定理。

• 看不懂。