函數漸進界的性質研究

楊冀林

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.在年終考核時，考核政策應當向生活教師適度傾斜。原因在于，學校以教學為主，作為負責學生安全和后勤工作的生活教師往往會受到忽視，其工作上的辛勤付出往往無法得到與之匹配的重視和關照，影響其工作積極性。而通過適度的考核政策傾斜，能夠讓生活教師充滿干勁，以更為飽滿的工作熱情投入到其本職工作之中。

證明1）若f（n）=O（g（n）），且g（n）=O（h（n）），則由定義1知，存在自然數n1和正常數c1，當n≥n1時，有f（n）≤ c1g（n），同時存在自然數n2和正常數c2，當n≥n2時，有g（n）≤c2h（n），取n0=max{n1，n2}，當n≥n0時，有f（n）≤c1g（n） ≤c1c2h（n）=c · h（n）（c=c1c2）

根據定義1有f（n）=O（h（n））。

定理3：設f（n），g（n）是定義在自然數集N上的兩個非負實值函數，則有以下結論：

于是，根據定義定義3有f（n）=Θ（h（n））。

定理4：設f（n），g（n）是定義在自然數集N上的兩個非負實值函數，若對于某個其它的非負實值函數h（n）有f（n）=O（h（n）），g（n）=O（h（n）），則有f（n）+g（n）=O（h（n））。

證明：由于f（n）=O（h（n）），所以存在自然數n1和正常數c1，當n≥n1時，有f（n）≤c1h（n）

同理由于g（n）=O（h（n）），所以存在自然數n2和正常數c2，當n≥n2時，有f（n）≤c2h（n）取n0=max{n1，n2}當n=n0時，由以上二式有：f（n）+g（n）≤（c1+c2）h（n）=c·h（n）（c=c1+c2），所以有f（n）+g（n）=O（h（n））。

則有f（n）+g（n）=Θ（f（n））。

定理5：設f（n），g（n）是定義在自然數集N上的兩個非負實值函數，則有：

max{f（n），g（n）}=Θ（f（n）+g（n））。

證明：不妨假設max{f（n），g（n）} =f（n），于是g（n）≤f（n），所以 f（n）+g（n）≤2f（n）

另一方面由于f（n），g（n）的非負性，顯然有f（n）≤f（n）+ g（n）

從而有f（n）=O（f（n）+g（n）），即有

由（1）（2）式得到max{f（n），g（n）}=Θ（f（n）+g（n））。

1）若 ，則p（n）=O（nk）

2）若 ，則p（n）=Ω（nk）

3）若 ，則p（n）=Θ（nk）

結論1）2）的證明類似，僅證結論1）和3）。

此外，函數漸進的界還有一些算法中常用的性質，限于篇幅列出不予證明：

1）任何常函數都是Ο（1），Ω（1），Θ（1）

2）Ο（cf）=Ο（f），Ω（cf）=Ω（f），Θ（cf）=Θ（f），其中是c正常數。

3）Ο（f ·g）=Ο（f）·Ο（g），Ω（f ·g）=Ω（f）·Ω（g），Θ（f ·g）=Θ（f）·Θ（g），

3 結論

函數漸進的界有許多重要性質，本文給出函數漸進界的概念及幾何解釋，Ο，Ω，Θ，ο符號及其等價性，分類歸納出算法分析中常用的一些性質，并利用極限理論給予嚴格的數學證明，這無疑將對系統掌握函數漸進界的性質，提高算法復雜度的分析能力提供有益的幫助。

[1]霍衛紅,算法設計與分析[M].西安電子科技大學出版社，2005：8-11.

[2]Jon Kleiberg,Eva Tardos,算法設計[M].清華大學出版社,2007：25-30.

[3]M.H.Alsuwaiyel,算法設計技巧分析[M].電子工業出版社,2009：11-20.

[4]屈婉玲,算法分析與計算復雜性理論講義,2010：27-31.

[5]盧開澄,計算機算法導論[M].清華大學出版社,1996：9-10.

[6]王曉東,計算機算法設計與分析[M].電子工業出版社，2004：1-5.

[7]宋文,杜亞軍,算法設計與分析[M].重慶大學出版社：2004：5-7.