首页 > 代码库 > 算法导论 第三章 函数的成长

算法导论 第三章 函数的成长

渐近符号

Θ记号

Θ(g(n))={f(n):存在正常量c1,c2和n0,使得对所有n>=n0,都有0<=c1g(n)<=f(n)<=c2g(n)}

重点:

1.f(n)是Θ(g(n))的成员,至于f(n)=Θ(g(n))这种写法的原因后面会知道

2.根据P26可知,g(n) 是f(n)的一个渐进紧确界

3.当n足够大的时候,f(n)非负

 

O符号

O(g(n))={f(n):存在正常量c和n0,使得对所有n>=n0,有0<=f(n)<=cg(n)}

重点:

1.Θ记号渐近地给出了函数的上限和下限。当只有一个渐近上界时,使用O记号

2.按照集合论的写法,Θ(g(n))是O(g(n))的子集

3.当我们说运行时间为O(n^2),意思是存在一个为O(n^2)的函数f(n),使得对于n的任意值,不管选择什么特定的规模为n的输入,其运行时间的上界都是f(n),最坏情况运行时间就是O(n^2)

 

 Ω符号

Ω(g(n))={f(n):存在正常量c和n0,使得对所有n>=n0,有0<=cg(n)<=f(n)}

 

定理3.1 对于任意两个函数f(n)和g(n),我们有f(n)=Θ(g(n))且当f(n)=O(g(n))和f(n)=Ω(g(n))

 

等式与不等式的渐近符号

 

算法导论 第三章 函数的成长