下面四种记号是为了建立函数间的相对级别。 CLRS上的一张图很直观：
大O记号
定义：如果存在正常数\(c\)和\(n_0\)，使得当\(N\ge n_o\)时\(T(N)\le cf(N)\)，记\(T(N)=O(f(N))\)。
举个栗子： 当\(N < 1000\)时，\(1000N\gt N^2\)，但\(N^2\)增长率更大，所以最终\(N^2\)会更大，即\(O(N^2)=1000N\)。
也就是说，总会存在某个点\(n_0\)，从这个点以后\(cf(N)\)至少和\(T(N)\)一样大，忽略常数因子，即\(T(N)\)的增长率小于等于\(f(N)\)的增长率。
那么为什么这个常数因子\(c\)可以忽略呢？ 当\(N\ge n_o\)时，\(T(N)\le cf(N)\)，也就是\(\frac{T(N)}{f(N)}\le c\)。此时如果\(T(N)\)的增长率大于\(f(N)\)的增长率，那么\(\frac{T(N)}{f(N)}\)不可能小于某个常数，也就是\(c\)不存在，与我们的前提条件矛盾，所以说忽略掉常数因子后，\(T(N)\)的增长率仍然小于等于\(f(N)\)的增长率。
那么既然\(T(N)\)是以不快于\(f(N)\)的速度增长，也就可以说\(f(N)\)是\(T(N)\)的一个上界(upper bound)，即最坏情况。
\(\Omega\)记号
定义：如果存在正常数\(c\)和\(n_0\)，使得当\(N\ge n_o\)时\(T(N)\ge cg(n)\)，记\(T(N)=\Omega(g(n))\)。
与上述大O的分析类似，可知： \(T(N)\)的增长率大于等于\(g(N)\)的增长率，\(g(N)\)是\(T(N)\)的一个下界(lower bound)，即最好情况。
\(\Theta\)记号
定义：当且仅当\(T(N)=\Omega(h(n))\)、\(T(N)=O(h(n))\)时， \(T(N)=\Theta(f(n))\)。
那么这个就是说\(T(N)\)的增长率等于\(h(N)\)的增长率，即最坏情况和最好情况相同。
小o记号
定义：若\(T(N)=O(p(n))\)且\(T(N)\neq\Theta(p(n))\)时， \(T(N)=o(f(n))\)。
与大O不同，小o表示\(T(N)\)的增长率小于\(p(N)\)的增长率，不包括等于。
