关于复杂度的一些基本的定义

来源于《数据结构与算法分析:C语言描述》

def1:如果存在正常数c和n0,使得当N>=n0时,T(N)<=cf(N),则记为T(N) = O(f(N));       T(N)的增长率小于等于f(N)的增长率

def2:如果存在正常数c和n0,使得当N>=n0时,T(N)>=cg(N),则记为T(N) = Ω(g(N));     T(N)的增长率大于等于g(N)的增长率

def3:   T(N) = θ(h(N))当且仅当T(N) = O(h(N)) && T(N) = Ω(h(N));                                  T(N)的增长率等于h(N)的增长率

def4:   如果T(N) = O(p(N))且T(N) != θ(p(N)),则T(N) = o(p(N))。                                     T(N)的增长率小于p(N)的增长率

原文地址:https://www.cnblogs.com/dzy521/p/9383185.html