渐近记号与主定理
渐近记号与主定理
渐近记号用来描述函数的运行时间，刻画运行时间的上界、确界、下界。使用递归定义的函数通常使用主定理分析时间复杂度。
一、渐近记号
本节定义一些基本函数，用于描述时间复杂度。
1.1 $\quad$ 渐进记号、函数与运行时间
1.1.1 $\quad$ $\Theta$ 记号
我们使用 $\Theta$ 记号描述函数的渐近紧确界。
形式化地， $\Theta (g(n))=\{f(n):\exists c_1,c_2,n_0:\forall n\ge n_0,0\le c_1g(n)\le f(n)\le c_2g(n) \}$。
其中，冒号意为“使得”。
也就是说，存在常量 $c_1,c_2,n_0$，可以将 $f(n)$ 夹入 $c_1g(n)$ 和 $c_2(n)$ 中。$\Theta(g(n))$ 要求每个成员 $f(n)\in \Theta(g(n))$ 渐近非负。
我们通常使用 $\Theta(1)$ 表示常量或某个变量的常量函数。
1.1.2 $\quad$ $O$ 记号
当函数只有一个渐近上界时，使用 $O$ 记号。
形式化地， $O (g(n))=\{f(n):\exists c,n_0:\forall n\ge n_0,0\le f(n)\le cg(n) \}$。
使用 $O$ 记号描述上界，我们常常可以检查算法的总体结构来描述算法运行的时间，如循环嵌套等，这里不再展开。
1.1.3 $\quad$ $\Omega$ 记号
$\Omega$ 记号提供了函数的渐近下界。
形式化地，$\Omega (g(n))=\{f(n):\exists c,n_0:\forall n\ge n_0,0\le cg(n)\le f(n)\}$。
我们不难有如下定理：
定理 $\quad$ 对于任意两个函数 $f(n),g(n)$，我们有 $f(n)=\Theta(g(n))$，当且仅当 $f(n)=O(g(n))$ 且 $f(n)=\Omega(g(n))$。
1.1.4 $\quad$ $o$ 记号
前面的 $O$ 记号描述的渐近上界，我们使用 $o$ 记号来描述一个非渐近紧确的上界，如 $2n=o(n^2)$ 而 $2n^2\not=o(n^2)$。
形式化地，$o (g(n))=\{f(n):\forall c>0,\exists n_0>0:\forall n\ge n_0, 0\le f(n) < cg(n) \}$。
直观上，在 $o$ 记号中，当 $n\rightarrow + \infty$，函数$f(n)$ 相对于 $g(n)$ 来说变得微不足道了。
1.1.5 $\quad$ $\omega$ 记号
我们使用 $\omega$ 记号描述一个非渐近紧确的下界。
形式化地，$\omega (g(n))=\{f(n):\forall c>0,\exists n_0>0:\forall n\ge n_0, 0\le cg(n) < f(n) \}$。
1.2 $\quad$ 渐近函数的性质
我们令 $f(n),g(n)$ 渐近为正。
渐近函数具有传递性，即 $f(n)=\Theta (g(n)),g(n)=\Theta h(n)\Rightarrow f(n)=\Theta(h(n))$。其他记号同理。
渐近函数具有自反性，即 $f(n)=\Theta f(n)$，对于 $O,\Omega$ 记号同理。
$\Theta$ 函数具有对称性，即 $f(n)=\Theta(g(n))$ 当且仅当 $g(n)=\Theta (f(n))$。
渐近函数具有转置对称性，即 $f(n)=O(g(n))$ 当且仅当 $g(n)=\Omega f(n)$；$f(n)=o(g(n))$ 当且仅当 $g(n)=\omega (f(n))$。
二、使用主方法求解递归式
对于类似
的递归式，通常使用主定理求解其渐近界。
2.1 $\quad$ 主定理
定理（主定理） $\quad$ 令 $a\ge 1$ 和 $b\ge 1$ 是常数，$f(n)$ 是一个函数，$T(n)$ 是定义在非负整数上的递归式：
我们将其中的 $n/b$ 解释为 $\lceil n/b \rceil$ 或者 $\lfloor n/b \rfloor$，那么 $T(n)$ 有如下渐近界：
- 若对某个常数 $\epsilon >0$ 有 $f(n)=O(n^{\log_b a-\epsilon})$，则有 $T(n)=\Theta(n^{\log_ba})$。
- 若 $f(n)=\Theta(n^{\log_b a})$，则 $T(n)=\Theta(n^{\log_b a}\lg n)$。
- 若对某个常数 $\epsilon>0$ 有 $f(n)=\Omega(n^{\log_b a+\epsilon})$，且对某个常数 $c<1$ 和所有足够大的 $n$ 有 $af(n/b)\le cf(n)$，则 $T(n)=\Theta(f(n))$。
上面就是主定理。注意这三种情况并未覆盖 $f(n)$ 的所有可能性，下面将说明如何正确地使用主定理。
2.2 $\quad$ 使用主方法
我们把使用主定理求解递归式的方法称为主方法。我们只需要确定一个递归式对于主定理的哪种情况成立，即可得到解。
例子 $\quad$ 对于下面的递归式，求解其渐近界。
对于这个递归式，我们有 $a=9,b=3,f(n)=n$，因此 $n^{\log b a}=b^{\log_3 9}=\Theta(n^2)$。由于 $f(n)=O(n^{\log_39-\epsilon})$，其中 $\epsilon=1$，因此可以应用于情况1，得到 $T(n)=\Theta(n^2)$。
例子 $\quad$ 对于下面的递归式，求解其渐近界。
其中，$a=1,b=\frac{2}{3},f(n)=1$，因此 $n^{\log_b a}=n^0=1$。由于 $f(n)=\Theta(n^{\log _b a})=\Theta(1)$，应用于情况2，得到 $T(n)=\Theta(\lg n)$。
例子 $\quad$ 对于下面的递归式，求解其渐近界。
其中，$a=3,b=4,f(n)=n\lg n$，因此 $n^{\log_b a}=O(n^{0.793})$。由于 $f(n)=\Omega(b^{\log_4 3-\epsilon})$，其中 $\epsilon\approx 0.2$，因此，如果可以证明正则条件成立，可应用于情况3。当 $n$ 足够大时，有 $af(n/b)\le cf(n)$，得到 $T(n)=\Theta(n\lg n)$。
上面给出了三种例子，只要算出 $n^{\log_b a}$ 的渐近界，与 $f(n)$ 比较，就可以求出递归式的渐近界。
