iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 5

Day-5 演算法分析工具 : 漸進式符號(Big-O, Big-Theta, Big-Omega)

前言

比較合併排序法與插入排序法,一旦輸入n的規模足夠大時,合併排序在最壞情況所需的時間Θhttps://chart.googleapis.com/chart?cht=tx&chl=(nlgn),而插入排序法在最壞情況所需的時間為Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2),當n足夠大時,合併排序法的效率遠遠超過插入排序法。對於足夠大的輸入,一個演算法所需的時間受到最高次項的影響要遠遠超過低次項與常數項,因此,在輸入夠大的情況會將其忽略。

當輸入夠大時,演算法所需的時間只和增加的量級有關,我們通常只關心演算法的漸進效率(asymptotic efficiency)。所謂漸進效率,即是當輸入的數量夠多時,演算法所需的時間和輸入的數量呈現怎樣的關係,是呈現線性關係,還是指數關係等等。

演算法常見的估計方法,漸進式符號(Asymptotic Notation)

用來描述演算法漸進運行時間的漸進式符號是以一個定義域為自然數集合https://chart.googleapis.com/chart?cht=tx&chl=N = { https://chart.googleapis.com/chart?cht=tx&chl=0%2C1%2C2%2C....}的函數來定義。而這樣定義函數的定義域有助於我們在處理最壞的情況,當然,我們也可以按照漸進符號的使用情況,讓這些符號的定義域在任意集合,如實數域等等集合。

前面我們寫到插入排序法的最差情況為Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2),使用Θ這個漸進符號來描述演算法所需要的時間。而Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)這樣的表示法,是由我們推導出來的https://chart.googleapis.com/chart?cht=tx&chl=an%5E2%2Bbn%2Bc所寫出來的,其中https://chart.googleapis.com/chart?cht=tx&chl=a%2Cb%2Cc這些皆為常數,通過寫成,漸進符號通常應用在函數或是多項式上。

漸進式分析是基於以下幾個觀點

  1. 忽略掉關於電腦運行速度的因素,那些因素會以常數符號c作為替代
  2. 不關心一個演算法的運行時間,而是關心他的增長量,也就是輸入規模n趨近於無限時。

所謂的漸進式符號,為描述演算法趨勢的一個函數集合。

Θ

給定一個函數https://chart.googleapis.com/chart?cht=tx&chl=g(n),使用Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))來表示以下函數的集合:

  • Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n)) = {https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3A 存在正實數https://chart.googleapis.com/chart?cht=tx&chl=c_1%2C%20c_2https://chart.googleapis.com/chart?cht=tx&chl=n_0使得對所有https://chart.googleapis.com/chart?cht=tx&chl=n%20%3E%3D%20n_0,有https://chart.googleapis.com/chart?cht=tx&chl=0%20%3C%3D%20c_1g(n)%20%3C%3D%20f(n)%20%3C%3D%20c_2g(n)}
    如果存在正整數https://chart.googleapis.com/chart?cht=tx&chl=c_1%2Cc_2,使得對於足夠大的n,https://chart.googleapis.com/chart?cht=tx&chl=f(x)能夠被https://chart.googleapis.com/chart?cht=tx&chl=c_1g(n)https://chart.googleapis.com/chart?cht=tx&chl=c_2g(n)之間,我們就可以說https://chart.googleapis.com/chart?cht=tx&chl=f(x)是屬於Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))這個函數集合中。

  • 我們具體的證明https://chart.googleapis.com/chart?cht=tx&chl=1%2F2n%5E2-3n%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)這個式子,令https://chart.googleapis.com/chart?cht=tx&chl=c_1%2Cc_2%2Cn_0屬於正整數集合,使得對所有https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3Dn_0,有
    https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2%3C%3D1%2F2n%5E2-3n%3C%3Dc_2n%5E2,把https://chart.googleapis.com/chart?cht=tx&chl=n%5E2除掉,得到
    https://chart.googleapis.com/chart?cht=tx&chl=c_1%3C%3D1%2F2-3%2Fn%3C%3Dc_2
    得到選擇任意https://chart.googleapis.com/chart?cht=tx&chl=c_2%3E%3D1%2F2,可以使得https://chart.googleapis.com/chart?cht=tx&chl=1%2F2-3%2Fn對於任意https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3D1的值成立,而對於https://chart.googleapis.com/chart?cht=tx&chl=c_1%3C%3D1%2F14,可以使https://chart.googleapis.com/chart?cht=tx&chl=1%2F2-3%2Fn對於任意https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3D7成立。因此,當https://chart.googleapis.com/chart?cht=tx&chl=c_1%3D1%2F14%2C%20c_2%3D1%2F2https://chart.googleapis.com/chart?cht=tx&chl=n_0%3D7,可以證明https://chart.googleapis.com/chart?cht=tx&chl=1%2F2n%5E2-3n%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)。當然,對於其他一些常數也是如此,重點是存在某一個常數,可以被包含在Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)這個函數集合中。

簡單來說,一個式子忽略掉常數和低階項,舉例:https://chart.googleapis.com/chart?cht=tx&chl=3n%5E3%20%2B%2090n%5E2%20-%205n%20%2B%206789%20%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E3)(注意: θ是大寫),他所表示的概念是大於等於並且小於等於。

  • 以集合的觀點看待,Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n)) = Ohttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))∩Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))

一般情況,會以https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))描述這樣的觀念,這裡的'='不是'等於'的意思,而是'屬於'的意思

在上圖我們可以看到函數https://chart.googleapis.com/chart?cht=tx&chl=c_1g(n)https://chart.googleapis.com/chart?cht=tx&chl=c_2g(n)將函數https://chart.googleapis.com/chart?cht=tx&chl=f(n)夾在中間。看到圖形的x軸,我們可以看到當https://chart.googleapis.com/chart?cht=tx&chl=n_0往n的方向逼近,https://chart.googleapis.com/chart?cht=tx&chl=f(n)的值是高於https://chart.googleapis.com/chart?cht=tx&chl=c_1g(n)但低於https://chart.googleapis.com/chart?cht=tx&chl=c_2g(n)的,換句話說,對所有https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3Dn_0,函數https://chart.googleapis.com/chart?cht=tx&chl=f(n)必然在n到https://chart.googleapis.com/chart?cht=tx&chl=n_0的範圍中,找到一個k使得https://chart.googleapis.com/chart?cht=tx&chl=f(k)%20%3D%20g(n),這時候我們會稱https://chart.googleapis.com/chart?cht=tx&chl=g(n)https://chart.googleapis.com/chart?cht=tx&chl=f(n)的一個漸進臨界線(asymptotically tight bound)。


Big-O

如果存在一個正實數c和https://chart.googleapis.com/chart?cht=tx&chl=n_0使得當https://chart.googleapis.com/chart?cht=tx&chl=N%20%3E%3D%20n_0https://chart.googleapis.com/chart?cht=tx&chl=T(N)%20%3C%3D%20cf(N),則表示為https://chart.googleapis.com/chart?cht=tx&chl=T(N)%20%3D%20O(f(N)),通常用於評估一個演算法最久要花費多少時間,也就是一個演算法的上限,小於等於的概念,一個演算法至少會小於等於Big-O函數集合的概念。

  • 另一種Big-O定義方式 : 假設存在兩常數https://chart.googleapis.com/chart?cht=tx&chl=c%20%3E%200%2C%20n_0%20%3E%200,使得https://chart.googleapis.com/chart?cht=tx&chl=0%20%3C%3D%20f(n)%20%3C%3D%20cg(n),對於所有https://chart.googleapis.com/chart?cht=tx&chl=n%20%3E%3D%20n_0皆成立,值得注意的一點為Big-O為非對稱符號(asymmetric),A = B不代表B = A。
  • 以集合觀點來定義Big-O,https://chart.googleapis.com/chart?cht=tx&chl=f(n)屬於https://chart.googleapis.com/chart?cht=tx&chl=g(n)的子集,集合中的元素皆為函數,我們可以定義https://chart.googleapis.com/chart?cht=tx&chl=O(g(N))%20%3D%20{ https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3A 為一個函數集合,存在https://chart.googleapis.com/chart?cht=tx&chl=c%20%3E%200%2C%20n_0%20%3E%200,使得https://chart.googleapis.com/chart?cht=tx&chl=f(n)以0和https://chart.googleapis.com/chart?cht=tx&chl=cg(n)為界,https://chart.googleapis.com/chart?cht=tx&chl=0%20%3C%3D%20f(n)%20%3C%3D%20cg(n),對所有https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3D%20n_0皆成立 },也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)的漸進成長率小於https://chart.googleapis.com/chart?cht=tx&chl=g(n)

另外一個集合的觀點,我們可以發現https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))這個觀念中,其實蘊含https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20O(g(n))這個概念。

Example 1 : https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2%20%3D%20O(n%5E3)https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2小於或是等於https://chart.googleapis.com/chart?cht=tx&chl=n%5E3,根據上面的定義,我們不能說https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2等於https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E3),我們只能說https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2是屬於https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E3)的子集。因此這裡的等號需要理解成屬於某個集合的概念,更精確的寫法,也可以寫https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2%20https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E3)

Example 2 : https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20n%5E3%20%2B%20O(n%5E2),表示存在一個函數https://chart.googleapis.com/chart?cht=tx&chl=h(n)https://chart.googleapis.com/chart?cht=tx&chl=%20O(n%5E2)使得https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20n%5E3%20%2B%20h(n)

Example 3 : https://chart.googleapis.com/chart?cht=tx&chl=n%5E2%20%2B%20O(n)%20%3D%20O(n%5E3),對所有函數https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20https://chart.googleapis.com/chart?cht=tx&chl=O(n),存在https://chart.googleapis.com/chart?cht=tx&chl=h(n)%20https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E2),使得https://chart.googleapis.com/chart?cht=tx&chl=n%5E2%20%2B%20f(n)%20%3D%20h(n)


Ω

如果存在一個正實數c和https://chart.googleapis.com/chart?cht=tx&chl=n_0使得當https://chart.googleapis.com/chart?cht=tx&chl=N%20%3E%3D%20n_0https://chart.googleapis.com/chart?cht=tx&chl=T(N)%20%3E%3D%20cg(N),則表示為https://chart.googleapis.com/chart?cht=tx&chl=T(N)%20%3D Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(N)),表是一個演算法的下界,也就是最好的情況,花最少時間的時候,大於等於的概念,一個演算法至少會大於等於Ω。

    • 以集合的觀點進行定義,Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))%20%3D { https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3A 存在常數https://chart.googleapis.com/chart?cht=tx&chl=%20c%20%3E%200%2C%20n_0%20%3E%200使得https://chart.googleapis.com/chart?cht=tx&chl=%200%20%3C%3D%20cg(n)%20%3C%3D%20f(n)%20對所有 https://chart.googleapis.com/chart?cht=tx&chl=n%20%3E%3D%20n_0}

Example 1 : √https://chart.googleapis.com/chart?cht=tx&chl=n = Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(lgn) 概念上為當n足夠大時,√https://chart.googleapis.com/chart?cht=tx&chl=n總是大於等於Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(lgn)


Little-o

我們上面介紹到Big-O這個漸進符號,但是我們可以發現到Big-O所提供的漸進情況可能不是精確的,像是https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2%3DO(n%5E2),這個使用Big-O的確是精確的上界,但是https://chart.googleapis.com/chart?cht=tx&chl=2n%3DO(n%5E2),雖然是函數的上界,但卻不是精確的。我們這裡使用little-o來表示一個非漸進式的精確上界。

  • https://chart.googleapis.com/chart?cht=tx&chl=o(g(n))%20%3D%20{https://chart.googleapis.com/chart?cht=tx&chl=f(n)對於任一正整數https://chart.googleapis.com/chart?cht=tx&chl=c%3E0,存在常數https://chart.googleapis.com/chart?cht=tx&chl=n_0%3E0,使得對所有https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3Dn_0,有https://chart.googleapis.com/chart?cht=tx&chl=0%3C%3Df(n)%3Ccg(n)}
    概念上就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)函數的增長率嚴格小於https://chart.googleapis.com/chart?cht=tx&chl=g(n)

Example 1 : https://chart.googleapis.com/chart?cht=tx&chl=2n%3Do(n%5E2),但是https://chart.googleapis.com/chart?cht=tx&chl=2n%5E2!%3Do(n%5E2)

比較Big-O和little-o之間的差別,Big-O為https://chart.googleapis.com/chart?cht=tx&chl=0%20%3C%3D%20f(n)%20%3C%3D%20cg(n),而little-o為https://chart.googleapis.com/chart?cht=tx&chl=0%3C%3Df(n)%3Ccg(n),兩者主要差別在https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3Do(g(n)),也就是函數的增長率是小於還是嚴格小於的差別,因此little-o是比Big-O還要來得強烈的敘述,little-o是比較小的函數集合。

  • ω(讀做little-omega),概念上是大於的概念,也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)增長率嚴格大於https://chart.googleapis.com/chart?cht=tx&chl=g(n)


來源

函數集合之間的比較關係

https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))%5C%20and%5C%20g(n)%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(h(n))蘊含https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(h(n))
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20O(g(n))%5C%20and%5C%20g(n)%3DO(h(n))蘊含https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3DO(h(n))
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))%5C%20and%5C%20g(n)%3DΩhttps://chart.googleapis.com/chart?cht=tx&chl=(h(n))蘊含https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3DΩhttps://chart.googleapis.com/chart?cht=tx&chl=(h(n))
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20o(g(n))%5C%20and%5C%20g(n)%3Do(h(n))蘊含https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3Do(h(n))
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))%5C%20and%5C%20g(n)%3Dωhttps://chart.googleapis.com/chart?cht=tx&chl=(h(n))蘊含https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3Dωhttps://chart.googleapis.com/chart?cht=tx&chl=(h(n))

https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))類似於https://chart.googleapis.com/chart?cht=tx&chl=a%3Db
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20O(g(n))類似於https://chart.googleapis.com/chart?cht=tx&chl=a%3C%3Db
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))類似於https://chart.googleapis.com/chart?cht=tx&chl=a%3E%3Db
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20o(g(n))類似於https://chart.googleapis.com/chart?cht=tx&chl=a%3Cb
https://chart.googleapis.com/chart?cht=tx&chl=f(n)%3D%20ωhttps://chart.googleapis.com/chart?cht=tx&chl=(g(n))類似於https://chart.googleapis.com/chart?cht=tx&chl=a%3Eb

小節

以上這一些定義目的在於為兩個函數之間提供一個可以相對比較的標的或是準則,給定兩個函數,通常函數上會存在一些點,在這一些點上函數值小於另一個函數的值或是大於函數得值,因此,像https://chart.googleapis.com/chart?cht=tx&chl=f(x)%20%3C%20g(x)這樣的表示事實上是不具有任何意義的。

於是,我們比較他們的相對遞增率(relative rate of growth),當我們將這個概念應用到演算法效率分析時,我們所進行的比較就能夠體現出意義了。

而上面這些用來描述一個演算法執行時間的函式,我們稱為該演算法的時間複雜度,如果使用Big-O對https://chart.googleapis.com/chart?cht=tx&chl=f(n)進行描述,會稱一個演算法的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(f(n))

參考資料: Introduciton to algorithms 3rd


上一篇
Day-4 演算法分析概念
下一篇
Day-6 Divide-and-Conquer-1 : merge sort
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言