渐进分析法

渐进分析:
1.渐进紧确界
Θ记号定义:
对一个给定的函数g(n),用Θ(g(n))来表示以下函数的集合:Θ(g(n))={T(n):存在c1,c2,n0>0,使得对所有n ≥ n0,有0≤ c1g(n) ≤T(n) ≤ c2g(n) }
2.渐进上界
O记号定义:
对一个给定的函数g(n),用Θ(g(n))来表示以下函数的集合:
Θ(g(n))={T(n):存在c,n0>0,使得对所有n ≥ n0,有0≤ T(n) ≤ cg(n) }
3.渐进下界
Ω记号定义:
对一个给定的函数g(n),用Θ(g(n))来表示以下函数的集合:
Θ(g(n))={T(n):存在c,n0>0,使得对所有n ≥ n0,有0≤ cg(n) ≤ T(n) }

上一篇:数据结构复习之哈夫曼树及应用


下一篇:如何检测或判断一个文件或字节流(无BOM)是什么编码类型