计算理论 复杂度预备知识

计算理论 复杂度预备知识

符号

$f(n)=o(g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)<cg(n)$ ；$\sum _{n\to \infty }\frac{f(n)}{g(n)}=0$ ；
$f(n)=O(g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)\le cg(n)$ ；
$f(n)=\theta (g(n))$ ：$\exists c_1,c_2$ ，当 $n$ 足够大时， $c_{1}g(n)<f(n)<c_{2}g(n)$ ；
$f(n)=\omega (g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)>cg(n)$ ；
$f(n)=\Omega (g(n))$ ：$\exists c$ ，当 $n$ 足够大时， $f(n)\ge cg(n)$ ；

递归表达式求解通项公式

① $T(n)=4T\left(\frac{n}{2}\right)+n$ ：就直接展开，找到规律
$$\begin{array}{l}T(n)\\ =4T(\frac{n}{2})+n\\ =4(4(T(\frac{n}{2^2})+\frac{n}{2})+n\\ =4T(\frac{n}{2^2})+2n+n\\ =4^{k}T(\frac{n}{2^k})+n(2^0+2^1+\cdots +2^{k-1})\end{array}$$
假设 $n$ 是 2 的幂，则最后 $k$ 应该等于 ${\log }_2(n)$ ，故：
$$T(n)=T(1)n^2+n\sum _{i=1}^{{\log }_2(n)}{2}^{i-1}=T(1)n^2+n(n-1)=O(n^2)$$
② $T(n)=2T(\frac{n}{2})+n=nT(1)+n{\log }_2(n)=O(n\log n)$
③ $T(n)=4T(\frac{n}{2})+n^2=n^{2}T(1)+n^2{\log }_{2}n=O(n^2\log n)$
④ $T(n)=2T(\frac{n}{2})+n^2=nT(1)+2n^2=O(n^2)$
⑤ $T(n)=4T(\frac{n}{2})+\frac{n^2}{\log n}$
$$\begin{array}{l}T(n)\\ =4T(\frac{n}{2})+\frac{n^2}{\log n}\\ =n^{2}T(1)+\frac{n^2}{\log n}+\frac{n^2}{\log n-1}+\cdots +\frac{n^2}{\log 1}\\ =\theta (n^2\log \log n)\end{array}$$
因为这个级数可以看成积分：
$$\frac{1}{x}+\frac{1}{x-1}+\frac{1}{x-2}+\cdots ={\int }_1^{x}dx=\ln x$$

主方法

Th：设 $a\ge 1$ ，$b\ge 1$ ，$f(n)$ 为一定义在非负整数上的函数，$T(n)=aT(\frac{n}{b})+f(n)$ （当 $\frac{n}{b}$ 不为整数时代表 $\lceil \frac{n}{b}\rceil$ 或 $\lfloor \frac{n}{b}\rfloor$ ），则：

1. 若 $\exists \epsilon >0$ ，使得 $f(n)=O(n^{{\log }_{b}a-\epsilon })$ ，则 $T(n)=\Theta (n^{{\log }_{b}a})$
2. 若 $\exists k\ge 0$ ，使得 $f(n)=\Theta (n^{{\log }_{b}al{g}^{k}n})$ ，则 $T(n)=\Theta (n^{{\log }_{b}a}l{g}^{k+1}n)$
3. 若 $\exists \epsilon >0$ ，使得 $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ ，且存在 $0<c<1$ 以及正整数 $N_0$ ，使得当 $n>N_0$ 时，有 $af(\frac{n}{b})\le cf(n)$ ，则 $T(n)=\Theta (f(n))$
   证明：首先展开，得到：

$$\begin{array}{l}T(n)\\ =aT(\frac{n}{b})+f(n)\\ =a(aT(\frac{n}{b^2})+f(\frac{n}{b}))+f(n)\\ a^{2}T(\frac{n}{b^2})+af(\frac{n}{b})+f(n)\\ =\dots \\ =a^{{\log }_{b}n}T(1)+\sum _{i=0}^{{\log }_{b}n-1}{a}^{i}f(\frac{n}{b^i})\end{array}$$

其中 $a^{{\log }_{b}n}=b^{{\log }_{b}a{\log }_{b}n}=n^{{\log }_{b}a}$ ；如果把 $f(n)$ 看成多项式的话，只需要比较 $f(n)$ 的次数与 ${\log }_{b}a$ 的相对大小；
① 若 $\exists \epsilon >0$ ，使得 $f(n)=O(n^{{\log }_{b}a-\epsilon })$ ，则 $T(n)=\Theta (n^{{\log }_{b}a})$
$$\begin{array}{l}\sum _{i=0}^{{\log }_{b}n-1}{a}^{i}f\left(\frac{n}{b^i}\right)\\ =\sum a^i{\left(\frac{n}{b}\right)}^{{\log }_{b}a-\epsilon }\\ =\sum \frac{n^{{\log }_{b}a-\epsilon }-b^{i\epsilon }}{a^i}\\ =n^{{\log }_{b}a-\epsilon }\sum b^{i\epsilon }\\ =n^{{\log }_{b}a-\epsilon }\frac{1-n^{\epsilon }}{1-b^{\epsilon }}\\ =O(n^{{\log }_{b}a})\end{array}$$
② 若 $\exists k\ge 0$ ，使得 $f(n)=\Theta (n^{{\log }_{b}al{g}^{k}n})$ ，则 $T(n)=\Theta (n^{{\log }_{b}a}l{g}^{k+1}n)$
我们就假设 $f(n)=n^{{\log }_{b}a}{\lg }^{k}n$ ，则：
$$\begin{array}{l}\sum _{i=0}^{{\log }_{b}n-1}{a}^{i}f\left(\frac{n}{b^i}\right)\\ =\sum a^i(\frac{n}{b^i}{)}^{{\log }_{b}a}{\lg }^k(\frac{n}{b^i})\\ =\sum a^i\frac{n^{{\log }_{b}a}}{a^i}(\lg n-i\lg b{)}^k\end{array}$$
这个 $(\lg n-i\lg b{)}^k$ 二项展开的话会发现，次数肯定是 ${\lg }^{k}n$ 决定的，则：
$$\begin{gathered} \begin{array}{l}\approx \sum n^{ \\ lo{g}_{b}a}{\lg }^{k}n\\ ={\log }_{b}n\cdot n^{ \\ lo{g}_{b}a}{\lg }^{k}n\\ =n^{{\log }_{b}a}l{g}^{k+1}n\end{array} \end{gathered}$$
③ 若 $\exists \epsilon >0$ ，使得 $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ ，且存在 $0<c<1$ 以及正整数 $N_0$ ，使得当 $n>N_0$ 时，有 $af(\frac{n}{b}\le cf(n))$ ，则 $T(n)=\Theta (f(n))$
当满足条件时，有 $cf(n)\ge af(\frac{n}{b})$ ，得到：
$$f(n)\ge \frac{a}{c}f(\frac{n}{b})\ge \frac{a^2}{c^2}f(\frac{n}{b^2})\ge \cdots \ge \frac{a^i}{c^i}f(\frac{n}{b^i})$$
故 $f(n)\ge \frac{a^i}{c^i}f(\frac{n}{b^i})$ ；需要满足所有大于等于的条件，发现只需要最后一个大于等于满足即可，即 $\frac{n}{b^i}>N_0⟹i<{\log }_{b}n-{\log }_b{N}_0+1$
$$\begin{array}{l}\sum _{i=0}^{{\log }_{b}n-1}{a}^{i}f\left(\frac{n}{b^i}\right)\\ =\sum _{i=0}^{{\log }_b^n-{\log }_b^{N_0}}{a}^{i}f\left(\frac{n}{b^i}\right)+\sum _{i={\log }_b^n-{\log }_b^{N_0}+1}^{{\log }_{b}n-1}{a}^{i}f\left(\frac{n}{b^i}\right)\end{array}$$
左项是满足 $i<{\log }_{b}n-{\log }_b{N}_0+1$ 的条件，有：
$$\le \sum _{i=0}^{{\log }_b^n-{\log }_b^{N_0}}{c}^{i}f(n)=O(f(n))$$
右项是 $O(1)$ ，展开也看不出来（直接把 $f(n)$ 看作 $O(n^{{\log }_{b}a+\epsilon })$）：
$$\begin{array}{l}=\sum a^i{\left(\frac{n}{b^i}\right)}^{{\log }_{b}a+\epsilon }\\ =\sum a^i\frac{n^{{\log }_{b}a+\epsilon }}{a^i\cdot b^{i\epsilon }}\\ =n^{{\log }_{b}a+\epsilon }\sum \frac{1}{b^{i\epsilon }}\\ =\frac{1-({\frac{1}{b}}^{\epsilon }{)}^{{\log }_b{N}_0-1}}{1-\frac{1}{b^{\epsilon }}}\cdot \frac{1}{b^{\epsilon ({\log }_{b}n-{\log }_b{N}_0+1)}}\cdot n^{{\log }_{b}a+\epsilon }\end{array}$$
第一项是常数，后边两项乘起来看着像个常数

Akra-Bazzi 定理

Th：设 $g(x)$ 为一非负函数，$T(x)=\{\begin{array}{ll}\Theta (1)& ,1\le x\le X_0\\ \sum _{i=1}^k{a}_{i}T(\frac{x}{b_i})+g(x)& ,n>X_0\end{array}$ （其中 $k\ge 1$ ，$a_i>0$ ，$b_i>1$，$X_0$ 满足对任意 $1\le i\le k$ 有 $X_0>b_i$ 且 $X_0>\frac{b_i}{b_i-1}$ ），若 $g(x)$ 满足多项式增长条件，$p$ 为方程 $\sum _{i=1}^k\frac{a_i}{b_i^p}=1$ 的实数解，则：
$$T(x)=\Theta \left(x^p\left(1+{\int }_1^x\frac{g(x)}{x^{p+1}}dx\right)\right)$$
例：$T(n)=2T(\frac{n}{4}+3T(\frac{n}{6})+n\lg n)$
解 $\frac{2}{4^p}+\frac{3}{6^p}=1$ 得 $p=1$
$$\begin{array}{l}T(n)\\ =\Theta (n(1+{\int }_1^n\frac{x\lg x}{x^2}dx))\\ =\Theta (n(1+\frac{1}{2}{\lg }^{2}n))\\ =\Theta (n{\lg }^{2}n)\end{array}$$