时间复杂度符号

- `Upd 2020/4/3`：修了下 `MD` 和 $\KaTeX$ 和语言描述。 - [CSDN拓展](https://blog.csdn.net/CHIERYU/article/details/50432699) ------ ### 五种符号： $Θ$，读音：$\mathrm{theta}$、西塔；既是上界也是下界（$\textsf{tight}$），等于的意思。 $O$，读音：$\mathrm{big-oh}$、欧米可荣（大写）；表示上界($\textsf{tightness\;unknown}$)，小于等于的意思。 $ο$，读音：$\mathrm{small-oh}$、欧米可荣（小写）；表示上界($\textsf{not\;tight}$)，小于的意思。 $Ω$，读音：$\mathrm{big\;omega}$、欧米伽（大写）；表示下界($\textsf{tightness\;unknown}$)，大于等于的意思。 $ω$，读音：$\mathrm{small\;omega}$、欧米伽（小写）；表示下界($\textsf{not\;tight}$)，大于的意思。 ----- ### 解释： 大 $O$ 符号（英语：$\mathfrak{Big\;O\;notation}$）是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。 大 $Ω$ 符号的定义与大 $O$ 符号的定义类似，但主要区别是，大 $O$ 符号表示函数在增长到一定程度时总小于一个特定函数的**常数倍**，大 $Ω$ 符号则表示总大于，来描述一个函数数量级的渐近下界。 大 $Θ$ 符号是大 $O$ 符号和大 $Ω$ 符号的结合。下面给出具体的数学定义: 函数$f(n)$代表某一算法在输入大小为$n$的情况下的工作量（效率），则在$n$趋向很大的时候，我们将$f(n)$与另一行为已知的函数$g(n)$进行比较： 1) 如果 $\lim\;\dfrac{f(n)}{g(n)}=0$，则称 $f(n)$ 在数量级上严格小于 $g(n)$，记为 $f(n)=ο(g(n))$； 2) 如果 $\lim\;\dfrac{f(n)}{g(n)}=\infty$，则称 $f(n)$ 在数量级上严格大于 $g(n)$，记为 $f(n)=ω(g(n))$； 3) 如果 $\lim\;\dfrac{f(n)}{g(n)}=c$，这里 $c$ 为非 $0$ 常数，则称 $f(n)$ 在数量级上等于 $g(n)$，即 $f(n)$和$g(n)$ 是同一个数量级的函数，记为 $f(n)=Θ(g(n))$； 4) 如果$f(n)$在数量级上小于或等于$g(n)$，则记为 $f(n)=O(g(n))$； 5) 如果$f(n)$在数量级上大于或等于$g(n)$，则记为 $f(n)=Ω(g(n))$； - 一句话：大 $O$ 大 $Ω$ 都是存在 $c$，小 $o$ 小 $ω$ 都是任意 $c$。