「算法导论」渐进记号&主定理 学习笔记 (咕)

引入

有一天， $author$ 看到一个神奇的式子：

$$\large T(n)=9T(\frac n 3)+n$$

现求：上式的时间复杂度

可怜的 $author$ 做不出来，于是就进行一番神奇的操作，最后在某本厚得可以拿来防身的黑书上找了这神奇的解法——主定理

主定理：用渐进符号表示许多由分治法得到的递推关系式的方法

渐进记号

要求：对于渐进记号中所有函数，均是渐进非负，也就是所谓的渐进正函数（对足够大的 $n$ 均为正的函数）

渐进记号一览：

渐进紧确记号：$\Theta$

渐进上界记号：$O$

渐进下界记号：$\Omega$

非渐进紧确上界记号：$o$

非渐进紧确下界记号：$\omega$

$\Theta$ 记号

读作：$/‘θi:tə/$，$LaTeX$ 语法：\Theta

对一个给定的函数 $g(n)$，用 $\Theta(g(n))$ 来表示一下函数的集合：

$\Theta(g(n))={\ f(n)$：存在正常量 $c_1$、$c_2$ 和 $n_0$，使得对所有 $n\ge n_0$，有 $0\le c_1g(n)\le f(n)\le c_2g(n)\ }$

我们称 $g(n)$ 是 $f(n)$ 的一个渐进紧确界 $(asymptotically\ tight\ bound)$

$O$ 记号

读作：$/əu/$，$LaTeX$ 语法：O （别看了，就是字母O

对一个给定的函数 $g(n)$，用 $O(g(n))$ (读作”大 $Og(n)$ “，有时仅读作”$Og(n)$ “)来表示一下函数的集合：

$O(g(n))=${ $f(n)$：存在正常量 $c$ 和 $n_0$，使得对所有 $n\ge n_0$，有 $0\le f(n)\le cg(n)$ }

$O$ 记号提供了渐进上界

$\Omega$ 记号

读作：$/oʊ’meɡə/$，$LaTeX$ 语法：\Omega

对一个给定的函数 $g(n)$，用 $\Omega(g(n))$ 来表示一下函数的集合：

$\Omega(g(n))=${ $f(n)$：存在正常量 $c$ 和 $n_0$，使得对所有 $n\ge n_0$，有 $0\le cg(n)\le f(n)$ }

$\Omega$ 记号提供了渐进下界

主定理

令 $a\ge 1$ 和 $b>1$ 是常数，$f(n)$ 是一个函数，$T(n)$ 是定义在非负整数上的递归式：

$$\large T(n)=aT(\frac n b)+f(n)$$

其中我们将 $\frac n b$ 解释为 $\lfloor \frac n b \rfloor$ 或 $\lceil \frac n b \rceil$。那么 $T(n)$ 有如下渐进界：

1. 若对某个函数 $\epsilon >0$ 有 $f(n)=O(n^{\log_b{a-\epsilon }})$，则 $T(n)=\Theta(n^{\log_ba})$。
2. 若 $f(n)=\Theta(n^{\log_ba})$，则 $T(n)=\Theta(n^{\log_ba}\lg n)$。
3. 若对某个常数 $\epsilon>0$ 有 $f(n)=\Omega(n^{\log_ba+\epsilon})$，且对某个函数 $c<1$ 和所有足够大的 $n$ 有 $af(\frac n b) \le cf(n)$，则 $T(n)=\Theta(f(n))$。