下面四种记号是为了建立函数间的相对级别。
CLRS上的一张图很直观:大O记号
定义:如果存在正常数cc和n0n0,使得当N≥noN≥no时T(N)≤cf(N)T(N)≤cf(N),记T(N)=O(f(N))T(N)=O(f(N))。
举个栗子:
当N<1000N<1000时,1000N>N21000N>N2,但N2N2增长率更大,所以最终N2N2会更大,即O(N2)=1000NO(N2)=1000N。也就是说,总会存在某个点n0n0,从这个点以后cf(N)cf(N)至少和T(N)T(N)一样大,忽略常数因子,即T(N)T(N)的增长率小于等于f(N)f(N)的增长率。
那么为什么这个常数因子cc可以忽略呢?
当N≥noN≥no时,T(N)≤cf(N)T(N)≤cf(N),也就是T(N)f(N)≤cT(N)f(N)≤c。此时如果T(N)T(N)的增长率大于f(N)f(N)的增长率,那么T(N)f(N)T(N)f(N)不可能小于某个常数,也就是cc不存在,与我们的前提条件矛盾,所以说忽略掉常数因子后,T(N)T(N)的增长率仍然小于等于f(N)f(N)的增长率。那么既然T(N)T(N)是以不快于f(N)f(N)的速度增长,也就可以说f(N)f(N)是T(N)T(N)的一个上界(upper bound)。
ΩΩ记号
定义:如果存在正常数cc和n0n0,使得当N≥noN≥no时T(N)≥cg(n)T(N)≥cg(n),记T(N)=Ω(g(n))T(N)=Ω(g(n))。
与上述大O的分析类似,可知:
T(N)T(N)的增长率大于等于g(N)g(N)的增长率,g(N)g(N)是T(N)T(N)的一个下界(lower bound)。ΘΘ记号
定义:当且仅当T(N)=Ω(h(n))T(N)=Ω(h(n))、T(N)=O(h(n))T(N)=O(h(n))时,
T(N)=Θ(f(n))T(N)=Θ(f(n))。那么这个就是说T(N)T(N)的增长率等于h(N)h(N)的增长率。
小o记号
定义:若T(N)=O(p(n))T(N)=O(p(n))且T(N)≠Θ(p(n))T(N)≠Θ(p(n))时,
T(N)=o(f(n))T(N)=o(f(n))。与大O不同,小o表示T(N)T(N)的增长率小于p(N)p(N)的增长率,不包括等于。