前言

比較合併排序法與插入排序法，一旦輸入n的規模足夠大時，合併排序在最壞情況所需的時間Θ，而插入排序法在最壞情況所需的時間為Θ，當n足夠大時，合併排序法的效率遠遠超過插入排序法。對於足夠大的輸入，一個演算法所需的時間受到最高次項的影響要遠遠超過低次項與常數項，因此，在輸入夠大的情況會將其忽略。

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

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

用來描述演算法漸進運行時間的漸進式符號是以一個定義域為自然數集合 = { }的函數來定義。而這樣定義函數的定義域有助於我們在處理最壞的情況，當然，我們也可以按照漸進符號的使用情況，讓這些符號的定義域在任意集合，如實數域等等集合。

前面我們寫到插入排序法的最差情況為Θ，使用Θ這個漸進符號來描述演算法所需要的時間。而Θ這樣的表示法，是由我們推導出來的所寫出來的，其中這些皆為常數，通過寫成，漸進符號通常應用在函數或是多項式上。

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

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

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

Θ

給定一個函數，使用Θ來表示以下函數的集合:

• Θ = { 存在正實數和使得對所有，有}
  如果存在正整數，使得對於足夠大的n，能夠被和之間，我們就可以說是屬於Θ這個函數集合中。

• 我們具體的證明Θ這個式子，令屬於正整數集合，使得對所有，有
  ，把除掉，得到
  
  得到選擇任意，可以使得對於任意的值成立，而對於，可以使對於任意成立。因此，當且，可以證明Θ。當然，對於其他一些常數也是如此，重點是存在某一個常數，可以被包含在Θ這個函數集合中。

簡單來說，一個式子忽略掉常數和低階項，舉例:Θ(注意: θ是大寫)，他所表示的概念是大於等於並且小於等於。

• 以集合的觀點看待，Θ = O∩Ω

一般情況，會以Θ描述這樣的觀念，這裡的'='不是'等於'的意思，而是'屬於'的意思

在上圖我們可以看到函數和將函數夾在中間。看到圖形的x軸，我們可以看到當往n的方向逼近，的值是高於但低於的，換句話說，對所有，函數必然在n到的範圍中，找到一個k使得，這時候我們會稱是的一個漸進臨界線(asymptotically tight bound)。

Big-O

如果存在一個正實數c和使得當時,則表示為，通常用於評估一個演算法最久要花費多少時間，也就是一個演算法的上限，小於等於的概念，一個演算法至少會小於等於Big-O函數集合的概念。

• 另一種Big-O定義方式 : 假設存在兩常數，使得，對於所有皆成立，值得注意的一點為Big-O為非對稱符號(asymmetric)，A = B不代表B = A。
• 以集合觀點來定義Big-O，屬於的子集，集合中的元素皆為函數，我們可以定義{ 為一個函數集合，存在，使得以0和為界，，對所有皆成立 }，也就是的漸進成長率小於

另外一個集合的觀點，我們可以發現Θ這個觀念中，其實蘊含這個概念。

Example 1 : ，小於或是等於，根據上面的定義，我們不能說等於，我們只能說是屬於的子集。因此這裡的等號需要理解成屬於某個集合的概念，更精確的寫法，也可以寫∈ 。

Example 2 : ，表示存在一個函數 ∈使得

Example 3 : ，對所有函數∈ ，存在∈ ，使得

Ω

如果存在一個正實數c和使得當時 ,則表示為 Ω，表是一個演算法的下界，也就是最好的情況，花最少時間的時候，大於等於的概念，一個演算法至少會大於等於Ω。

• • 以集合的觀點進行定義，Ω { 存在常數使得對所有 }

Example 1 : √ = Ω 概念上為當n足夠大時，√總是大於等於Ω

Little-o

我們上面介紹到Big-O這個漸進符號，但是我們可以發現到Big-O所提供的漸進情況可能不是精確的，像是，這個使用Big-O的確是精確的上界，但是，雖然是函數的上界，但卻不是精確的。我們這裡使用little-o來表示一個非漸進式的精確上界。

• {對於任一正整數，存在常數，使得對所有，有}
  概念上就是函數的增長率嚴格小於

Example 1 : ，但是

比較Big-O和little-o之間的差別，Big-O為，而little-o為，兩者主要差別在，也就是函數的增長率是小於還是嚴格小於的差別，因此little-o是比Big-O還要來得強烈的敘述，little-o是比較小的函數集合。

• ω(讀做little-omega)，概念上是大於的概念，也就是增長率嚴格大於

來源

函數集合之間的比較關係

ΘΘ蘊含Θ
蘊含
ΩΩ蘊含Ω
蘊含
ωω蘊含ω

Θ類似於
類似於
Ω類似於
類似於
ω類似於

小節

以上這一些定義目的在於為兩個函數之間提供一個可以相對比較的標的或是準則，給定兩個函數，通常函數上會存在一些點，在這一些點上函數值小於另一個函數的值或是大於函數得值，因此，像這樣的表示事實上是不具有任何意義的。

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

而上面這些用來描述一個演算法執行時間的函式，我們稱為該演算法的時間複雜度，如果使用Big-O對進行描述，會稱一個演算法的時間複雜度為

參考資料: Introduciton to algorithms 3rd