下面四种记号是为了建立函数间的相对级别。
CLRS上的一张图很直观:
大O记号
定义:如果存在正常数(c)和(n_0),使得当(Nge n_o)时(T(N)le cf(N)),记(T(N)=O(f(N)))。
举个栗子:
当(N < 1000)时,(1000Ngt N^2),但(N^2)增长率更大,所以最终(N^2)会更大,即(O(N^2)=1000N)。
也就是说,总会存在某个点(n_0),从这个点以后(cf(N))至少和(T(N))一样大,忽略常数因子,即(T(N))的增长率小于等于(f(N))的增长率。
那么为什么这个常数因子(c)可以忽略呢?
当(Nge 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),使得当(Nge 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)
eqTheta(p(n)))时,
(T(N)=o(f(n)))。
与大O不同,小o表示(T(N))的增长率小于(p(N))的增长率,不包括等于。