《算导》整理·渐进记号
silverxz
·
·
个人记录
这篇文章是对五种渐进记号（Θ、O、Ω、o、ω）的整理。加深一下自己的理解。
先说一下渐进记号是干什么的吧。
渐进记号通常是用来描述一个函数的增长趋势的，或许也正是因此，《算法导论》中介绍渐进记号的章节的名字是“函数的增长”。也正是因此，渐进记号可以用来刻画算法的时间复杂度与空间复杂度。
OIer可能更熟悉的是，用“O”记号刻画算法的复杂度。这看起来没有什么问题，毕竟大家都用得好好的，至少“看起来”是这样。不过也仅仅是“看起来”而已。很多时候，O记号并不能很准确地描述算法的时空复杂度，甚至有的时候（比如用于描述下界）是荒唐的（我们后面会看到）。
另外，滥用O记号可能会使文章的逻辑混乱，尤其是在推导复杂度的时候。
因此，学会合理运用渐进记号是有必要的，至少可以用来装逼，不是么？
当然，这里要说明一下：对于大多数OIer来说，O记号已经足够用了（纵然可能使用不当）。渐进记号的使用几乎并不能影响您的OI成绩，所以这篇文章的受众（如果存在的话）应该是以这篇文章扩充知识面或是打发时间为目的。
现在，我们正式开始正文部分：
（对了，忘了说了：我们接下来涉及到的函数，如果没有特殊说明，默认是非负的。）
1.Θ记号及其使用
先上定义：
> 对于一个给定的函数$g(n)$，用$Θ(g(n))$来表示一下函数的集合：
> $Θ(g(n))$={ $f(n)$: 存在正常量$c_1$、$c_2$和$n_0$，使得对于所有$n>=n_0$，有$0 <= c_1g(n) <= f(n) <= c_2g(n)$ }
啧啧啧……看懂了吗？
看懂了当然最好，没看懂也无妨，我后续还会做一些说明帮助各位理解。
首先，Θ记号表示的是一个函数的**集合**，也就是满足条件的一类函数。
这个条件是什么样的呢？
感性地理解一下，就是**n足够大的时候，函数$f(n)$应该被夹在$c_1g(n)$和$c_2g(n)$之间**：
这样的$f(n)$就是符合条件的。因为$Θ(g(n))$是集合，$f(n)$是集合中的一个元素，所以我们本应该用$f(n)∈Θ(g(n))$来描述两者之间的关系。然而这样并不是很方便，所以我们通常**略作活用**，用$f(n)=Θ(g(n))$来表示这个关系。
这样做并不是没有理由。它可以给我们带来方便~~，虽然在这里不太看得出来~~。
到这里，你应该差不多明白$Θ$记号的含义了。对于满足$f(n)=Θ(g(n))$的$f(n)$，我们称$g(n)$是$f(n)$的**渐进紧确界**，因为它同时用上界和下界“束缚”住了$f(n)$（后面会看到只有上界和只有下界的情况，那就不是渐进紧确的了）。
我们再举几个栗子。
有如下几个函数：
$g(n)=n^2
f_1(n)=n^2
f_2(n)=100n^2+999n+100000
f_3(n)=0.001n^3
首先，很容易看出，f_1(n)=Θ(g(n))。只要任取0<c_1<=1和c_2>=1，就可以满足Θ记号的条件。
第二个可能具有一点点的迷惑性。然而大多数OIer都应该看得出来——f_2(n)=Θ(g(n))，当n足够大的时候，后面的低阶项是可以被忽略的。
而第三个，f_3(n)≠Θ(g(n))，当n足够大的时候，前面的系数起到的作用也不大。实际上，f_3(n)=Θ(n^3)。
上述三个栗子对于初步分析过算法复杂度的OIer应该都不会有任何难度。从直觉上来看，我们需要做的是：扔掉低阶项、忽略最高阶项的系数。而这样做也的确是对的。
2.O记号及其使用
终于到了大家都熟悉的O记号了。这个记号我们一般读作“O”，或者读作“大O”（因为后面还有小o，加以区分）。
与Θ记号不同的是，O记号仅仅对上界进行了描述。它的定义如下：
对于一个给定的函数g(n)，用O(g(n))来表示一下函数的集合：
和Θ记号是不是非常相似？Θ记号渐进地给出了函数的上界和下界，而O记号仅仅给出了函数的上界（突然想起那个典故：下面没有了也（逃））。
上图片：
有了Θ记号的基础，想必很容易就可以理解O记号——比Θ记号少了一个限定条件嘛。
但是！！
这一个限定条件其实很重要。记得在本文开始的时候我说过什么么：
很多时候，O记号并不能很准确地描述算法的时空复杂度，甚至有的时候（比如用于描述下界）是荒唐的（我们后面会看到）。
看下面这个例子：
g(n) = n^3
f(n) = n
那么这个命题：f(n) = O(g(n))是正确的么？你的第一反应可能是：当然不对，f(n) = O(n)才对！但其实，f(n) = O(n)是对的，而f(n) = O(n^3)也是对的！
这就是O记号的局限性——它只描述了上界，而下界是任意的。因此，O记号给出的界限往往不一定是准确的。
也正是因此，有时用O记号描述下界会很荒唐。我们来看一道《算导》中的习题：
练习3.1-3 解释为什么“算法A的运行时间至少是O(n^2)”这一表述是无意义的。
仔细想一想就可以明白：O(n^2)只给出了一个上界，而没有给出下界。给它冠以“至少”的限定是无意义的。O记号通常用来描述上界，如算法最坏情况时的复杂度。后面我们会给出一个可以描述下界的渐进记号。
3.Ω记号及其使用
想必很多人已经猜到了$Ω$记号的定义：
> 对于一个给定的函数$g(n)$，用$Ω(g(n))$来表示一下函数的集合：
> $Ω(g(n))$={ $f(n)$: 存在正常量$c$和$n_0$，使得对于所有$n>=n_0$，有$0 <= cg(n) <= f(n)$ }
再放一张图：
$Ω$记号仅仅给出的渐进下界。与$O$记号类似的是，我们不能说“算法A的运行时间至多是$Ω(n^2)$”，这是无意义的。
有了前两个记号的讲述，$Ω$记号很容易理解，这里就不赘述了（才发现我写了好长。。）
***
是不是觉得我要开始讲第四个了？错！
接下来要说的是一个定理：
> 对于任意的两个函数$f(n)$和$g(n)$，我们有$f(n) = Θ(g(n))$，当且仅当$f(n) = O(g(n))$且$f(n) = Ω(g(n))
这个定理很易于理解：f(n) = O(g(n))给出了渐进上界，f(n) = Ω(g(n))给出了渐进下界。上界和下界“拼在一起”，就成了渐进紧确界，得到f(n) = Θ(g(n))。通常，在f(n) = Θ(g(n))难以直接证明的时候，会分别证明其上界和下界，最后用此定理证明紧确界。
可以通过渐进记号的定义进行严谨的证明，不多说了。
好，我们继续。
4.o记号及其使用
$O$记号给出的渐进上界可能是也可能不是渐进紧确的；$o$记号给出的渐进上界一定不是渐进紧确的。
我们把$o$记号和$O$记号的定义放在一起比对一下：
> $O(g(n))$={ $f(n)$: 存在正常量$c$ 和 $n_0$，使得对于所有$n>=n_0$，有$0 <= f(n) <= cg(n)$ }
> $o(g(n))$={ $f(n)$: _**对任意**_ 正常量$c$，存在 $n_0$，使得对于所有$n>=n_0$，有$0 <= f(n) < cg(n)$ }
这样就可以看出来了：$o$记号的范围更小，$o(g(n))$是$O(g(n))$的真子集（请原谅我打不出“含于”符号……）。比如，$n^2 = O(n^2)$，但$n^2 ≠ o(n^2)$。$o$记号给出的是一个很宽松的上界。
这样看来，在$n$非常大，甚至趋于无穷的时候，$f(n)$相对于$g(n)$来说就微不足道了。因此，根据《算导》所述，有些学者把下面这个极限作为$o$记号的定义：
$${\lim_{n \to \infty} {\frac{f(n)} {g(n)} } } = 0$$
## 5.ω记号及其使用
$ω$记号和$Ω$记号很像，它们之间的区别，和$o$记号与$O$记号的区别差不多：
$Ω$记号给出的渐进下界可能是也可能不是渐进紧确的；$ω$记号给出的渐进下界一定不是渐进紧确的。
我们把两者的定义对比一下：
> $Ω(g(n))$={ $f(n)$: 存在正常量$c$和$n_0$，使得对于所有$n>=n_0$，有$0 <= cg(n) <= f(n)$ }
> $ω(g(n))$={ $f(n)$: _**对任意**_ 正常量$c$，存在 $n_0$，使得对于所有$n>=n_0$，有$0 <= cg(n) < f(n)$ }
有了$o$记号的讲述，这里就不再多说了。
同样，$n$非常大，甚至趋于无穷的时候，$g(n)$相对于$f(n)$也变得微不足道了，因此$ω$记号也有另一种定义：
$${ \lim_{n \to \infty} { \frac{f(n)} {g(n)} } } = \infty$$
除此之外，$ω$记号和$o$记号还有这样一种关系：
> $f(n) ∈ ω(g(n))$当且仅当$g(n) ∈ o(f(n))
这也是很易于理解的。
哇哈哈哈！是不是没想到还有？
6.渐进记号的性质
以下性质由定义易得，不证明。
1.传递性。
若f(n) = Θ(g(n))且g(n) = Θ(h(n))，则有f(n) = Θ(h(n))
该性质对其它渐进记号也成立。
2.自反性。
f(n) = Θ(f(n))
该性质对O和Ω成立，但是对o和ω不成立。
3.对称性。
f(n) = Θ(g(n))$当且仅当$g(n) = Θ(f(n))
f(n) = O(g(n))$当且仅当$g(n) = Ω(f(n))
f(n) = o(g(n))$当且仅当$g(n) = ω(f(n))
emmm……该说的差不多就都说完了，让我们留一点课后作业吧（手动滑稽）
我们都知道，n!是n的阶乘的意思。
试证明：
n! = o(n^n)
n! = ω(2^n)
再根据斯特林近似公式：
n! = \sqrt{2 \pi n}(\frac{n}{e})^n(1 + Θ(\frac 1 n))
证明（虽说不用那个公式，用积分近似的方式也可以证明）：
lg(n!) = Θ(nlgn)
注意！据《算导》所述，计算机科学家发现2是对数最自然的底，故在此定义：
lgn = log_{2}{n}
这也解决了我长久以来的疑惑，为什么很多算法明明是二分却要写nlgn……虽说在数学里lgn = log_{10}{n}……
这篇文章到此为止就真的结束了……应该是不会有人看的，所以这篇文章算是写给自己的吧，作为一个温习与加深理解的方式。
现学{L_aT^ex}，好累……
内容及习题整理自《算法导论》，强烈推荐，她是我现任女朋友。
图片出自Moonsmile的简书文章：算法基础+分治策略（算法复习第1弹），他写的很好，清楚简练。