原文: 函數漸近界及漸近符號介紹
date: 2020-12-24 22:39:04
前言
在在在計算機算法設計和復雜性分析中, 函數漸近界與算法復雜度分析有著很多聯(lián)系.
比如我們在算法復雜度分析中最常見到的大O符號（Big O notation）, 同時它在數學中是有著嚴謹的定義和證明
本節(jié)內容主要是引申到函數的漸近, 對其概念, 性質及一些分析行為做一些補充, 包括:
- 函數漸近界和漸近符號的介紹
- 非漸近緊確界的簡單介紹
- O,Ω,Θ 漸近符號的性質及其等價性
- 函數漸近比較的方式和示例
- 求漸近界的方法及示例分析
漸近界介紹
定義
函數的漸近界通常用漸近符號來表達, 也稱漸近記號, 首先來看最為常見的三種:
O big-oh: upper bound 漸近上界
- 函數f(n) = O(g(n)): 當且僅當存在正常數c, n0, 使得n>=n0時, 有
f(n) <= c*g(n)
Ω big-omega: lower bound 漸近下界
- 函數f(n) = Ω(g(n)): 當且僅當存在正常數c, n0, 使得n>=n0時, 有
f(n) >= c*g(n)
Θ theta: average bound 平均界 || asymptotically tight bound 漸近緊確界(緊確/確: 表示嚴格) || 緊致界
- 函數f(n) = θ(g(n)): 當且僅當存在正常數c1, c2, n0, 使得當n>=n0時, 有
c1*g(n) < f(n) <= c2*g(n)
**注意: **
- 有的漸近記號我用了多個中文描述或翻譯, 是因為很多時候中文叫法也不太相同, 所以不要搞混了
- 當且僅當: “在辑莫，并且僅僅在這些條件成立的時候”的縮寫，在英語中的對應標記為iff
借助這張圖更為直觀的理解一下
O(g(n))是一個集合, 所以實際上 f(n) ∈ O(g(n))
通常我們記作 f(n) = O(g(n)) 以表達相同的概念, 其它幾個記號同理.
示例
看一個簡單的例子分析: f(n) = 2n+3 , 求它的漸近上界O
首先代入定義中的不等式, 即 2n+3 <= cg(n)
你可以代入數字一個一個去試, 但是比較簡單的方法是把左邊的低階項提高然后放到右邊
即: 2n + 3 <= 2n+3n ==> 2n + 3 <= 5n
- 其中c=5, g(n)=n;
**因為: ** 存在正常數c=5, 當n>=(n0=1)時, 使得不等式 2n + 3 <= 5n 恒成立, 滿足O定義;
**所以: ** f(n)=O(n);
在這里可以看出, 對于不等式 2n+3 <= cg(n) 來說, 右邊的cg(n)不止只有 5n 才滿足定義
e.g. cg(n)可以是3n(c=3, n0=3), 100n(c=100, n0=1) 都是成立的.
甚至你可以寫它的高階 n^2(c=1, n0=3), 此時 f(n) = O(n^2) 這也是成立的, 所以只要滿足定義即可
Ω和θ也可以結合其定義用類似的方法得到:
- f(n) = Ω(n)
- f(n) = θ(n)
注意理解 f(n) = O(n) 這種寫法表達什么意思, 有時候還會描述成 2n+3=O(n) 這樣的寫法
可以簡單總結一下, 對于上述例子來說:
- n右邊的都可以說是f(n)的上界
- n左邊的都可以說是f(n)的下界
- 中間n就是平均界
你可以選擇更為高階的g(n)作為上界, 但那并不實用, 所以我們通常傾向于選擇最為接近的g(n)來作為上界; 下界的選擇同理.
分析
從上面這個梨子, 我們直觀感覺到, 似乎通過以下3步就能滿足漸近記號定義中的不等式:
- 去掉低階項并忽略高階項的系數
- O定義中的常量c取一個稍大于f(n)最高階項系數的值
- Ω定義中的常量c取一個稍小于f(n)最高階項系數的值
這種感覺是很實用的, 下面來用一個函數f(n)來驗證下: 從已知f(n)與θ反證定義中的c1, c2, n0
f(n) = 0.5n^2 - 3, f(n) = θ(n^2)
所以只要存在正常量c1, c2, n0, 使得所有n>n0時, 滿足:
c1n^2 <= 0.5n^2 - 3 <= c2n^2
這里假設取:
- c1=0.25, n>(n0=12)
- c2=0.5, n>(n0=0)
此時存在c1, c2, 使得當n > (n0=12) 時滿足不等式 0.25n^2 <= 0.5n^2 - 3 <= 0.5n^2
這里可以運用一些去通項來化簡不等式, 既而得到c1, c2, n0 (滿足存在即可, 并不是唯一)
這里用一個更直觀的方式看看:
理解了簡單的漸近界的分析方法, 那么它們三個的關系就可以用下面這個定理來表達:
- 對任意兩個函數f(n)和g(n), 我們有f(n)=θ(g(n)), 當且僅當f(n)=O(g(n))且f(n)=Ω(g(n))
例如: f(n)=an^2 + bn + c , f(n)=θ(n^2) ==> f(n)=O(n2) 且 f(n)=Ω(n2)
需要注意的是并不是從漸近確界得出漸近上界和下界, 而通常是用漸近上界和下界來證明漸近確界
**哪個對我們更有用? **
一開始我會有這兩個疑問, 對于一個函數f(n)來說:
- 是否需要把它的三種漸近界都求出 ?
- 通常情況下我們更關注哪個更有用 ?
首先: 上面示例中的函數比較簡單, 所以三種界都可以得到, 而在實際中, 并不一定(下面有這樣的示例)
每當一個函數, 如果你能用Theta(θ)表達是最好的, 如過無法得到它, 那么可以用BigO或Omega(Ω)來表達上界或下界
原因也很簡單, 因為θ能夠表達一個相較O與Ω更緊密精確的界限
就像我在完全不懂手機價格行情的情況下要買一部手機,
它可以告訴我3000, 4000(市場平均)的價格, 也可以告訴我100(市場最低) 或是10w(市場最高)的價格.
雖然這幾種回答都是正確的, 但很明顯平均價對我來說更有用
所以: 在這3種描述記號中, 如果給到的是O與Ω, 那么對方就不會確定這是不是最為接近的表達,
因為它可能是一個接近的, 也可能是一個較大或較小的值, 所以如果能給到θ是最好的
非漸近緊確界
介紹
通過對上面漸近上界, 漸近下界, 漸近緊確界的了解, 非漸近緊確界的概念就很好理解了,
它也有對應的兩個漸近記號o(小o) 與 **ω(小歐米伽) **: 用來表示非漸近緊確的上界和下界
上面介紹的O漸近上界與Ω漸近下界, 可能是漸近緊確的也可能不是漸近緊確的
例如對函數 f(n)=2n^2來說 { Ω(n^2), Ω(n), Ω(logn) } 都符合其漸近下界Ω的定義
Tip: 通常我們都會選擇最接近的界, 因為它最實用
但是只有 Ω(n^2) 是漸近緊確的, 其余幾個都是非漸近緊確的
所以漸近上界和下界又可細分為: 漸近緊確的 和 非漸近緊確的
定義
o: 非漸近緊確上界
- 函數f(n) = o(g(n)): 對任意正常數c, 存在n0, 使得n>=n0時, 有f(n) <= c*g(n)
ω: 非漸近緊確上界
- 函數f(n) = ω(g(n)): 對任意正常數c, 存在n0, 使得n>=n0時, 有f(n) >= c*g(n)
注意這里對正常數c的描述是"任意", 而不局限特定某個范圍, 這也是與O與Ω的最明顯區(qū)別
也可用極限函數來表述o與ω的定義:
o:
- 表示當n趨于無窮大時, f(n)相對g(n)來說非常非常非常小
ω:
- 表示當n趨于無窮大時, f(n)相對g(n)來說非常非常非常大
此外: 還有一種表述: f(n)∈ω(g(n)) 當且僅當 g(n)∈o(f(n))
漸近符號性質
基本性質
主要是這幾個: 整體性, 自反性, 傳遞性, 對稱性, 轉置對稱性
1. 整體性
注: Ω, O, θ都成立
If f(n) is O(g(n)), Then af(n) is O(g(n))
e.g. f(n) = 2n^2 + 5 is O(n^2)==> 10f(n) = f(20n^2 + 50) is O(n^2)
2. 自反性
f(n) is O(f(n))
e.g. f(n) = n^2 ==> f(n) is O(n^2)
有點奇怪, 但也比較好想, 因為一個函數的上限可以是任意大于等于它的函數, 所以一個函數可以是它自己的上限
3. 傳遞性
If f(n) is O(g(n)) and g(n) is O(h(n)) Then f(n) is O(h(n))
用文字來描述就是當函數g是函數f的上限, 并且函數h是函數g的上限, 那么函數h也是函數f的一個上限函數
e.g. f(n) = n , g(n) = n^2 , h(n) = n^3
n is O(n^2) and n^2 is O(n^3)
then n is O(n^3)
4. 對稱性
注: 只在θ成立
If f(n) is θ(g(n)), Then g(n) is θ(f(n))
e.g. f(n) = n^2 , g(n) = n^2
Then: f(n) = θ(n^2), g(n) = θ(n^2)
5. 轉置對稱性
注: 只在Ω與O成立
If f(n) is O(g(n)), Then g(n) is Ω(f(n))
用文字描述就是: 如果函數f是函數g的上限, 那么b函數就是a函數的下限 (我是你哥哥, 你就是我弟弟)
e.g. f(n) = n , g(n) = n^2
Then n is O(n^2) and n^2 is Ω(n)
反之亦然: If f(n) = Ω(g(n)) Then g(n) is O(f(n))
其它性質
除此之外, 還有幾個重要的性質
- If f(n) = O(g(n)) and f(n) = Ω(g(n)), Then f(n) = θ(g(n))
這個比較簡單, 之前已經有這樣的函數示例了
- 兩個函數相加的界
If f(n) = O(g(n)) and d(n) = O(e(n)), Then f(n) + d(n) = O(Max(g(n), e(n)))
e.g. f(n) = n = O(n) , d(n) = n^2 = O(n^2)
Then f(n) + d(n) = n + n^2 = On^2()
- 兩個函數相乘的界
If f(n) = O(g(n)) and d(n) = O(e(n)),
Then f(n) * d(n) = O((g(n) * e(n)))
因為這些性質的成立, 所以可以在兩個函數f與g的漸近比較中與實數a與b的比較之間做一種類比:
| 漸進界 | 類似于 |
|---|---|
| f(n) = O(g(n)) | a <= b |
| f(n) = Ω(g(n)) | a >= b |
| f(n) = θ(g(n)) | a == b |
| f(n) = o(g(n)) | a < b |
| f(n) = ω(g(n)) | a > b |
例如: 若f(n) = O(g(n)), 則可稱f(n)的漸近小于等于g(n)
它們在范圍上類似的幾何描述
函數的漸近比較
方式 & 示例
通常有兩種方式來比較兩個漸近函數的大小:
- 代入法
- 兩邊套上log
代入法比較簡單了, 代入數值去比較就可以了, 但缺點是你要代入足夠多的數值才可以, 就不說了
示例: 比較 n^2 與 n^3
這里為了書寫簡便, 就不寫函數的漸近表示了, 直接用函數表達式
所以來看下用套上log的方法, 用步驟來表示比較過程:
-
——
-
——
-
——
可得結果, 前者小于后者
兩邊log的方式在處理復雜函數時比較有用, 上面這兩個函數用肉眼就能判斷大小了, 所以看著不明顯
再來兩個比較復雜的函數:
示例一:
比較 f(n) = n^2*logn 與 g(n) = n* (logn)^10
-
——
-
——
-
——
可得前者 > 后者
示例二:
比較 與
(注:
)
-
——
-
(注:
)
-
忽略系數后是一樣的, 所以就函數漸近程度比較來說兩者相同
常用log公式
補充一些常用的log公式:
更多示例
幾個求O, Ω, Θ的例子來加深理解
Case 1: f(n) = 2n^2 + 3n + 4
2n^2 + 3n + 4 <= ``2n^2 + 3n^2 + 4n^22n^2 + 3n + 4 <= 9n^2
**∵ **此時存在c=9, 使得當n>(n0=1)時滿足不等式
∴f(n) = O(n^2)
同樣, 可以得到f(n) = Ω(n^2) 與 f(n) = θ(n^2), 方法類似, 不在贅述
Case 2: f(n) = n^2logn + n
1*n^2logn <= n^2logn <= 10 * n^2logn
可以得到O, Ω, θ都是 n^2logn
Case 3: f(n) = n!
注: n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1
- 1 * 1 * 1 * ... * 1 <= n! <= n * n * n * ... * n
- 1 <= n! <= n^n
可以得到f(n) = O(n^n) 與 f(n) = Ω(1), 無法得到θ
Case 4: f(n) = logn!
- log(1 * 1 * 1 * ... * 1) <= logn! <= log(n * n * n * ... * n)
- log1 <= logn! <= logn^n
- log1 <= logn! <= nlogn
可以得到f(n) = O(nlogn) 與 f(n) = Ω(1), 無法得到θ
從Case 3 和 Case 4可以看出, 函數f中都是階乘函數, 只能得到上界和下界, 無法給出緊密界限
上面也說過, 能算出緊密界限當然是最好的, 當你不能用平均界限來表達一個函數時, 還可以描述它的上限或下限, 此時上限和下限就變得很有用了
總結
需要說明的是, 這個主題與函數一樣都來源于數學
只不過算法分析領域中運用到了這些數學的東西, 但是二者并不等同
所以不要將它與算法復雜度分析中的最好, 最壞, 平均情況混淆起來, 不然你可能會很困惑.
因為函數漸近界的性質在算法分析中有著重要應用, 所以了解這部分內容會對于理解漸近分析會有所幫助
對于這部分內容, 算是簡單的理解和總結, 更多細致的內容需要運用極限的理論給予嚴格的數學證明, 這里并不涉及
所以理解上面的理論定義和示例分析對我來說已完全足夠, 對通常的算法分析來說也已完全足夠,
甚至不了解這部分內容也不會對你做算法分析有什么大的影響.
摘自:
- 部分內容來自《算法導論》第3章: 函數的增長
