我們首先來明确一波這幾個符号的讀音和具體的含義：

• Θ：大Theta，漸進緊界，可類比于等号（=）
• O：字母大O，漸進上界，可類比于小于等于（<=）
• Ω：大Omega，漸進下界，可類比于大于等于（>=）
• o：字母小o，非漸進緊确上界，可類比于小于（<）
• ω：小omega，非漸進緊确下界，可類比于大于（>）

定義：存在正常數，，使得對于所有的時，有，則f(n)屬于集合，記作。作為代替，我們通常記。

f(n) = Θ(g(n))

假設算法A的運行時間表達式為：

假設算法B的運行時間表達式為：

當問題規模足夠大的時候，例如n=100萬，算法的運行時間将主要取決于時間表達式的第一項，其它項的執行時間隻有它的幾十萬分之一，可以忽略不計。第一項的常數系數，随着n的增大，對算法的執行時間也變得不重要了。

所以，算法A的運行時間可以記為：；

算法B的運行時間可以記為：。

可以代入定義進行驗證：（以為例）

此時，我們隻需要取滿足條件的即可，很容易找到，即當時，有，滿足定義。注意，此處的取值不唯一，隻需要找到一組即可。

定義：設f(n)和g(n)是定義域為自然數集N上的函數。若存在正數c和，使得對一切，都有成立，則稱f(n)的漸進上界是g(n)，記作。通俗的說n滿足一定條件範圍内，函數f(n)的階不高于函數g(n)。

f(n) = O(g(n))

根據符号O的定義，用它評估算法的負載得到的桌子是問題規模充分大事件的一個上界。這個上界的階越低，評估越精确，越有價值。

例如，設，則

即可

即可，顯然，作為上界更為精确，更有價值。

這裡我們似乎就得到了Θ和O之間的關系，沒錯，那就是，我們可以由，可以看到這是一個不可逆的過程，也就是說，隻能由推出，不能逆向推導。

定義：設f(n)和g(n)是定義域為自然數集N上的函數。若存在正數c和，使得對一切，都有成立，則稱f(n)的漸進的下界是g(n)，記作。通俗的說n滿足一定條件範圍内，函數f(n)的階不低于函數g(n)。

f(n) = Ω(g(n))

根據符号Ω的定義，用它評估算法的負載得到的桌子是問題規模充分大事件的一個下界。這個下界的階越高，評估越精确，越有價值。

例如，設，則

f(n) = Ω(n)，取c=1,n_0=1即可

f(n) = Omega(n^2)，取c=1,n_0=1即可

f(n) =Omega(n^3)，取c=1,n_0=1即可，顯然，O(n^3)作為上界更為精确。

這裡我們似乎就得到了Θ和Ω之間的關系，沒錯，那就是，我們可以由，可以看到這是一個不可逆的過程，也就是說，隻能由推出，不能逆向推導。

定理：當且僅當有f(n) = Ω(g(n))且f(n) = O(g(n))，可以推出f(n) = Θ(g(n))。

這就給我們一個1思路，我們直接求Θ，直接找可能會很困難，此時我們可以通過求漸進上界，漸進下界來确定漸進緊界。

定義1：定義1：設f(n) 和g(n) 是定義域為自然數集N上的函數。若對于任意正數c，都存在，使得對一切，都有成立，則稱f(n)的漸進非緊确上界是g(n)，記作。通俗的說n滿足一定條件範圍内，函數f(n)的階低于函數g(n)。

定義2：設f(n)和g(n)是定義域為自然數集合的函數。如果 ，那麼。通俗理解為f(n)低于g(n)的階。

注意：這裡定義中的c不再是存在量詞而是全稱量詞，并且f(n)取不到cg(n)

定義1：定義1：設f(n) 和g(n) 是定義域為自然數集N上的函數。若對于任意正數c，都存在，使得對一切，都有成立，則稱f(n)的漸進非緊确下界是g(n)，記作。通俗的說n滿足一定條件範圍内，函數f(n)的階高于函數g(n)。

定義2：設f(n)和g(n)是定義域為自然數集合的函數。如果 ，那麼。通俗理解為f(n)高于g(n)的階。

注意：這裡定義中的c不再是存在量詞而是全稱量詞，并且f(n)取不到cg(n)

Θ、O、Ω、o、ω關系圖

1.算法導論 殷建平 譯   機械工業出版社

2.算法設計與分析 屈婉玲  著

3.算法設計與分析 王秋芬  呂聰穎著

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!