【软考】算法设计之渐进符号
什么是渐进符号呢？
答：在极限的角度看，只关心算法运行时间随着输入规模的无限增长而增长。其实我们经常使用的时间复杂度的O就是一种渐进符号，一种名为渐进上界的符号。
| 一、渐进上界 |
O记号，有着这样的等式 f(n) = O(g(n))
即为：存在正整数c和n0，使得对所有的n≥n0,有0 ≤ f(n) ≤ c*g(n)成立
如图：
例如：
| 二、渐进下界 |
Ω记号，有f(n) = Ω(g(n))
即为：存在正整数c和n0，使得对所有的n≥n0,有0 ≤ c*g(n)≤f(n) 成立
如图：
例如：
| 三、渐进紧致 |
Θ记号，有f(n) = Θ(g(n))
即为：存在正整数c1、c2和n0，使得对所有的n≥n0,有0 ≤ c1g(n)≤f(n) ≤ c2g(n)成立
如图：
例如：