20401

题目

使用主定理，求解以下递归式，并指出运用了主定理的哪种情况。

• (a) $T(n)=9T(n/3)+n^2$
• (b) $T(n)=T(2n/3)+\mathrm{\Theta }(1)$
• (c) $T(n)=3T(n/4)+n\lg n$
• (d) $T(n)=7T(n/2)+\mathrm{\Theta }(n^2)$
• (e) $T(n)=2T(n/2)+n^3$
• (f) $T(n)=4T(n/2)+\mathrm{\Theta }(n^2)$
• (g) $T(n)=2T(n/2)+n/\lg n$

解析

(a)

$a=9,b=3$, $f(n)=n^2$

$n^{{\log }_{b}a}=n^{{\log }_{3}9}=n^2$

由于 $f(n)=\mathrm{\Theta }(n^2)$, 符合情况 2。

所以 $T(n)=\mathrm{\Theta }(n^2\lg n)$。

(b)

$a=1,b=3$, $f(n)=\mathrm{\Theta }(1)$

$n^{{\log }_{b}a}=n^{{\log }_{3/2}1}=n^0=1$

由于 $f(n)=\mathrm{\Theta }(1)$, 符合情况 2。

因此，$T(n)=\mathrm{\Theta }(\lg n)$。

(c)

$a=3,b=4$, $f(n)=n\lg n$$n^{{\log }_{b}a}=n^{{\log }_{4}3}\approx n^{0.79}$ 由于 $f(n)=\mathrm{\Omega }(n^{{\log }_{4}3+ϵ})$ (取 $ϵ\approx 0.2$) 且满足正则性条件 $3f(n/4)\le \frac{3}{4}f(n)$，符合情况 3。 因此，$T(n)=\mathrm{\Theta }(n\lg n)$。

(d)

$a=7,b=2$, $f(n)=\mathrm{\Theta }(n^2)$

$n^{{\log }_{b}a}=n^{{\log }_{2}7}\approx n^{2.807}$

由于 $f(n)=O(n^{{\log }_{2}7-ϵ})$ (取 $ϵ\approx 0.8$)，符合情况 1。

因此，$T(n)=\mathrm{\Theta }(n^{{\log }_{2}7})$

(e)

$a=2,b=2$, $f(n)=n^3$

$n^{{\log }_{b}a}=n^{{\log }_{2}2}=n$

由于 $f(n)=\mathrm{\Omega }(n^{1+ϵ})$ (取 $ϵ=2$) 且满足正则性条件 $2f(n/2)=\frac{1}{4}f(n)$, 符合情况 3。

因此，$T(n)=\mathrm{\Theta }(n^3)$

(f)

$a=4,b=2$, $f(n)=\mathrm{\Theta }(n^2)$

$n^{{\log }_{b}a}=n^{{\log }_{2}4}=n^2$

由于 $f(n)=\mathrm{\Theta }(n^2)$, 符合情况 2。

因此，$T(n)=\mathrm{\Theta }(n^2\lg n)$

(g)

$a=2,b=2$, $n^{{\log }_{b}a}=n$。

现在我们比较 $f(n)$ 和 $n^{{\log }_{b}a}$：

• 情况 1: 是否存在 $ϵ>0$，使得 $f(n)=O(n^{{\log }_{b}a-ϵ})=O(n^{1-ϵ})$？

  我们计算比值的极限：$\underset{n\to \mathrm{\infty }}{lim}\frac{n/\lg n}{n^{1-ϵ}}=\underset{n\to \mathrm{\infty }}{lim}\frac{n^{ϵ}}{\lg n}=\mathrm{\infty }$。

  因为极限为无穷大，所以 $f(n)$ 的增长速度快于 $O(n^{1-ϵ})$。因此情况 1 不适用。

• 情况 2: 是否 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})=\mathrm{\Theta }(n)$？

  我们计算比值的极限：$\underset{n\to \mathrm{\infty }}{lim}\frac{n/\lg n}{n}=\underset{n\to \mathrm{\infty }}{lim}\frac{1}{\lg n}=0$。

  因为极限为 0，$f(n)$ 的增长速度慢于 $\mathrm{\Theta }(n)$，即 $f(n)=o(n)$。因此情况 2 不适用。

结论: $f(n)$ 正好落在了情况 1 和情况 2 之间：比 $n^{1-ϵ}$ 快，但比 $n$ 慢。因此，标准主定理无法直接求解此递归式。

根据 Akra-Bazzi 方法求解：

1. 找到 $p$ 使得 $\sum a_i{b}_i^p=1$。这里是 $2\cdot (1/2{)}^p=1⟹2^{1-p}=1⟹p=1$。

2. 根据公式 $T(n)=\mathrm{\Theta }\left(n^p(1+{\int }_1^n\frac{f(u)}{u^{p+1}}\mathrm{d}u)\right)$ 求解。

3. 代入参数：

   $T(n)=\mathrm{\Theta }\left(n^1(1+{\int }_c^n\frac{u/\lg u}{u^{1+1}}\mathrm{d}u)\right)$ (积分下界取常数 $c>1$ 以避免 $\lg 1=0$)

   $T(n)=\mathrm{\Theta }\left(n(1+{\int }_c^n\frac{1}{u\lg u}\mathrm{d}u)\right)$。

4. 求解积分：$\int \frac{1}{u\lg u}\mathrm{d}u$。令 $v=\lg u$，则 $\mathrm{d}v=\frac{1}{u\ln 2}\mathrm{d}u$。

   积分变为 $\int \frac{\ln 2}{v}\mathrm{d}v=(\ln 2)\ln v=(\ln 2)\ln (\lg u)$。

   所以，${\int }_c^n\frac{1}{u\lg u}\mathrm{d}u=[(\ln 2)\ln (\lg u){]}_c^n=(\ln 2)(\ln (\lg n)-\ln (\lg c))=\mathrm{\Theta }(\lg \lg n)$。

5. 代回原式：

   $T(n)=\mathrm{\Theta }(n(1+\mathrm{\Theta }(\lg \lg n)))=\mathrm{\Theta }(n\lg \lg n)$。