函数的渐近的界
$O$
定义如下：
设$f$和$g$是定义域为自然数集$N$上的函数，若存在正数$c$和$n_0$，使得对一切$n\geq n_0$有
成立，则称$f(n)$的渐进上界是$g(n)$，记作
- $f(n)$的阶不高于$g(n)$的阶
- 可能存在多个正数$c$，只要指出一个即可
- 对前面有限个$n$值可以不满足不等式
- 常函数的渐进上界可以写作$O(1)$
$\Omega$
定义如下：
设$f$和$g$是定义域为自然数集$N$上的函数，若存在正数$c$和$n_0$，使得对一切$n\geq n_0$有
成立，则称$f(n)$的渐进下界是$g(n)$，记作
- $f(n)$的阶不低于$g(n)$的阶
- 可能存在多个正数$c$，只要指出一个即可
- 对前面有限个$n$值可以不满足不等式
$o$
定义如下：
设$f$和$g$是定义域为自然数集$N$上的函数，若对于任意正数$c$都存在$n_0$，使得对一切$n\geq n_0$有
成立，则记作
- $f(n)$的阶低于$g(n)$的阶
- 对不同正数$c$，$c$越小$n_0$越大
- 对前面有限个$n$值可以不满足不等式
$\omega$
定义如下：
设$f$和$g$是定义域为自然数集$N$上的函数，若对于任意正数$c$都存在$n_0$，使得对一切$n\geq n_0$有
成立，则记作
- $f(n)$的阶高于$g(n)$的阶
- 对不同正数$c$，$c$越小$n_0$越小
- 对前面有限个$n$值可以不满足不等式
$\theta$
定义如下：
若$f(n)=O(g(n))=\Omega(g(n))$，则记作
- $f(n)$与$g(n)$的阶相等
- 对前面有限个$n$值可以不满足条件
定理
定理1
设$f$和$g$是定义域为自然数集合的函数
- 如果$lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}$存在，且等于某个常数$c>0$，那么$f(n)=\theta(g(n))$
- 如果$lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0$，那么$f(n)=o(g(n))$
- 如果$lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=+\infty$，那么$f(n)=\omega(g(n))$
一些重要结果：
多项式函数的阶低于指数函数的阶
$n^d=o(r^n)，r>1，d>0$
对数函数的阶低于幂函数的阶
$ln\ n=o(n^d)，d>0$
定理2
函数的阶之间的关系具有传递性，具体如下：
设函数$f、g、h$的定义域为自然数集合
- 如果$f=O(g)$且$g=O(h)$，那么$f=O(h)$
- 如果$f=\Omega(g)$且$g=\Omega(h)$，那么$f=\Omega(h)$
- 如果$f=\theta(g)$且$g=\theta(h)$，那么$f=\theta(h)$
定理3
设函数$f、g、h$的定义域为自然数集合，若对某个其它函数$h$，有$f=O(h)$和$g=O(h)$，那么$f+g=O(h)$。
该性质可以推广到有限个函数。
因为算法有有限步骤组成，根据每一步的时间复杂度函数上界，可以确定整个算法的时间复杂度函数上界。
几类重要函数
基本函数的分类
按照阶的高低分
至少指数级别
$2^n、3^n、n!$
多项式级
$n、n^2、n\,log\,n、\sqrt n$
对数多项式级
$log\,n、log^2n、log\,log\,n$
对数函数
一些符号如下：
- $log\,n=log_2n$
- $log^kn=(log\,n)^k$
- $log\,log\,n=log(log\,n)$
性质：
- $log_2n=\theta(log_ln)$
- $log_bn=o(n^\alpha)，\alpha>0$
- $a^{log_bn}=n^{log_ba}$
指数函数与阶乘
斯特林（Stirling）公式：
$n!=\sqrt{2\pi n}\ (\frac{n}{e})^n(1+\theta(\frac{1}{n}))$
$n!=o(n^n)$
$n!=\omega(2^n)$
$log(n!)=\theta(n\ log\ n)$
取整函数
- $x-1<\lfloor x\rfloor\leq x\leq\lceil x\rceil<x+1$
- $\lfloor x+n\rfloor=\lfloor x\rfloor+n，\lceil x+n\rceil=\lceil x\rceil+n，n为整数$
- $\lceil\frac{n}{2}\rceil+\lfloor\frac{n}{2}\rfloor=n$
- $\lceil\frac{\lceil\frac{n}{a}\rceil}{b}\rceil=\lceil\frac{n}{ab}\rceil，\lfloor\frac{\lfloor\frac{n}{a}\rfloor}{b}\rfloor=\lfloor\frac{n}{ab}\rfloor$
作者：@臭咸鱼
转载请注明出处：https://chouxianyu.github.io
欢迎讨论和交流!