函数渐进界的性质研究

杨冀林

YANG Ji-lin

（赤峰学院 计算机科学与技术系，赤峰 024000）

1 函数渐进界的定义

定义1：设f（n），g（n）是定义在自然数集N上的两个非负实值函数，如果存在自然数n0和正常数c，使得∀n≥n0，都有f（n）≤cg（n），则称g（n）是f（n）的一个渐进上界，记作f（n）=O（g（n））。

图1 渐近上界的几何解释

定义2：设f（n），g（n）是定义在自然数集N上的两个非负实值函数，如果存在自然数n0和正常数c，使得∀n≥n0，都有f（n）≤cg（n），则称g（n）是f（n）的一个渐进下界，记作f（n）=O（g（n））。

图2 渐近下界的几何解释

定义3：设f（n），g（n）是定义在自然数集N上的两个非负实值函数，如果存在自然数n0和两个正常数c1，c2使得∀n≥n0，都有c1g（n）≤f（n）≤c2g（n），则称g（n）是f（n）的紧致的界，记作f（n）=Θ（g（n））。

由定义可知f（n）=Θ（g（n）），当且仅当g（n）= Θ（f（n））。

定义4：设f（n），g（n）是定义在自然数集N上的两个非负实值函数，如果对每一个常数c＞0，都存在自然数n0，使得∀n≥n0，都有f（n）＜cg（n）则g（n）称是f（n）的一个上界，记作f（n）=o（g（n））。

图3 紧致界的几何解释

2 函数渐进界的性质

定理1 f（n）=Θ（g（n）） iff f（n）=O（g（n））且f（n）=Ω（g（n））。

证明⇒，若f（n）=Θ（g（n）），则根据定义3，存在自然数n0和正常数c1和c2，

使得当n≥n0时有c1g（n）≤f（n）≤c2g（n）。

由上式右边不等式可得f（n）=O（g（n））

由上式左边不等式可得f（n）=Ω（g（n））

⇒，若f（n）=O（g（n））且f（n）=Ω（g（n））

根据定义1，存在自然数n1和正常数c1，当n≥n1，有f（n）≤c1g（n） （1）

根据定义2，存在自然数n2和正常数c2，当n≥n2，有f（n）≤c2g（n） （2）

取n0=max{n1，n2}当n≥n0时，由（1）（2）式有c1g（n）≤f（n）≤c2g（n）

所以有f（n）=Θ（g（n））。

定理2 符号Ο，Ω，Θ，ο具有传递性，即有以下等式成立：

1）若f（n）=O（g（n）），且g（n）=O（h（n）），则f（n）= O（h（n））

2）若f（n）=Ω（g（n）），且g（n）=Ω（h（n）），则f（n）= Ω（h（n））

3）若f（n）=Θ（g（n）），且g（n）=Θ（h（n）），则f（n）= Θ（h（n））

4）若f（n）=o（g（n）），且g（n）=o（h（n）），则f（n）= o（h（n））

以上四个结论的证明是类似的，现只证明结论1）

4.在年终考核时，考核政策应当向生活教师适度倾斜。原因在于，学校以教学为主，作为负责学生安全和后勤工作的生活教师往往会受到忽视，其工作上的辛勤付出往往无法得到与之匹配的重视和关照，影响其工作积极性。而通过适度的考核政策倾斜，能够让生活教师充满干劲，以更为饱满的工作热情投入到其本职工作之中。……