函数的增长

[TOC]

渐进符号

渐进确界

$\Theta$

• 表示一个函数的上限与下限,可以理解为$f(n)$是集合$\Theta(n)$中的一个函数;

Θ(g(n)) = {f(n)：存在正常量$c_1,c_2$和$n_0$，使得对于所有的$n \geq n_0$，有$0 \leq c_1 * g(n) \leq f(n) \leq c_2 * g(n)$}

• 换句话说，对所有n≥n0，函数f(n)在一个常量因子内等于g(n)，这时称g(n)是f(n)的一个渐进紧确界；

  渐进非负，即当n足够大时，f(n)非负；

  渐进正函数，对所有足够大的n均为正的函数；

渐进上界

$O$

表示一个函数的上限,$O(g(n))$ = {$f(n)$:存在正常量$c$和$n_0$，使得对所有$n \geq n_0$,有$0 \leq f(n) \leq cg(n)$

渐进下界

$\Omega$

表示一个函数的下限, $\Omega (g(n))$ = {$f(n)$:存在正常量$c$和$n_0$，使得对所有$n \geq n_0$ ,有$0 \leq cg(n) \leq f(n)$；

定理

对任意两个函数$f(n)$和$g(n)$，我们有$f(n)=\Theta(g(n))$，当且仅当$f(n)=O(g(n))$且$f(n)=\Omega(g(n))$

等式和不等式的渐进符号

当渐进符号出现在等式中时，它一般代表某个我们不关注的匿名函数，这样可以帮助消除一个等式中无关紧要的细节与混乱；比如$2n^2+3n+1=2n^2+θ(n)$，$θ(n)$表示某个函数$f(n)$，该函数是集合$θ(n)$的某个函数；可以使用以下规则来解释：无论怎样选择等号左边的匿名函数，总有一种办法来选择等号右边的匿名函数使等式成立；换句话说，等式右边比左边提供的细节更粗糙。

非渐进紧确的上界

$o$

$o(g(n))$ = {$f(n)$:对于任一正常量$c>0$，存在常量$n_0>0$，使得对所有$n \geq n_0$,有$0 \leq f(n) \large \color{red}{<}$$cg(n)$，即

$\lim_{n \to +\infty} \frac{f(n)}{g(n)} = 0$

非渐进紧确的下界

$\omega$

定义的一种方式：$f(n) \in ω(g(n))$，当且仅当$g(n) \in ο(f(n))$；

$\omega(g(n))$ = {$f(n)$:对于任一正常量$c>0$，存在常量$n_0>0$，使得对所有$n \geq n_0$，有$0 \leq cg(n) \large \color{red}{<}$ $f(n)$}，即

$\lim_{n \to +\infty} \frac{f(n)}{g(n)} = \infty$

函数性质

三分性

对于任意两个实数a,b，下列三种情况恰有一种必须成立：$a>b,a=b,a<b$；但两个函数$f(n)$和$g(n)$，不是都可以渐进比较的；

标准记号与常规函数