算法导论笔记（四）算法分析常用符号-白红宇

算法导论笔记（四）算法分析常用符号

阅读量：4326 次

发布时间：2019-06-06

本文共 382 字，大约阅读时间需要 1 分钟。

♨ ${\color{Blue} f\left ( n \right )= \Theta \left ( g\left ( n \right ) \right )}$

{\color{Blue} f\left ( n \right )= \Theta \left ( g\left ( n \right ) \right )}

LaTeX

存在正常数 $c1$ 、 $c2$ 和 $n_{0}$ ，使任意 $n\geqslant n_{0}$ ，有 $0\leqslant c1g\left( n \right )\leqslant f\left ( n \right )\leqslant c2g\left ( n \right )$ 。

$\Theta \left ( g\left ( n \right ) \right )$ 其实是一个集合： $f\left ( n \right )\in\Theta \left ( g\left ( n \right ) \right )$ 。只是通常也写成标题那样而已。

♨ ${\color{Blue} f\left ( n \right )= O\left ( g\left ( n \right ) \right )}$

存在正常数 $c$ 和 $n_{0}$ ，使任意 $n\geqslant n_{0}$ ，有 $0\leq f\left ( n \right )\leq cg\left ( n \right )$ 。

$\Theta$ 强于 $O$ ，即 $\Theta \left ( g\left ( n \right ) \right )\subseteq O\left ( g\left ( n \right ) \right )$ 。

♨ ${\color{Blue} f\left ( n \right )= \Omega \left ( g\left ( n \right ) \right )}$

存在正常数 $c$ 和 $n_{0}$ ，使任意 $n\geqslant n_{0}$ ，有 $0\leq cg\left ( n \right )\leq f\left ( n \right )$ 。

♨ ${\color{DarkBlue} f\left ( n \right )= o\left ( g\left ( n \right ) \right )}$

$o$ 用来表示非渐进紧确上界。大 $O$ 和小 $o$ 的区别在于，大 $O$ 中的 $c$ 是某一常数，而小 $o$ 中的 $c$ 是任意大于０的常数，即： $\underset{n\rightarrow \infty}{lim}\frac{f\left ( n \right )}{g\left ( n \right )}= 0$ 。

\underset{n\rightarrow \infty}{lim}\frac{f\left ( n \right )}{g\left ( n \right )}= 0

LaTeX

♨ ${\color{DarkBlue} f\left ( n \right )=\omega \left ( g\left (n\right ) \right )}$

$\omega$ 与 $\Omega$ 的关系同大 $O$ 和小 $o$ 的关系。

意味着： $\underset{n\rightarrow \infty}{lim}\frac{f\left ( n \right )}{g\left ( n \right )}= \infty$ 。

转载于:https://www.cnblogs.com/AmitX-moten/p/4625690.html

你可能感兴趣的文章

小D课堂 - 新版本微服务springcloud+Docker教程_3-04 SpringCloud微服务核心组件Eureka介绍和闭源后影响...