演算法複雜度分析 決勝在數大時 中央大學 資工系 江振瑞 教授

1. 演算法的效能

演算法的效能 除了演算法的正確性之外，我們也關心演算法的效能(efficiency)，也就是討論演算法是否能夠使用較少資源而有效率地執行。 演算法執行時使用的資源有: 時間資源 記憶體資源 網路頻寬資源(當演算法需要透過網路傳輸資料時) 邏輯閘資源(當演算法使用邏輯閘實作時) … 在本課程我們聚焦於討論演算法執行時使用的時間資源與記憶體資源。

演算法的效能(續) 若我們能夠將所有的演算法以相同的高階程式語言實作，並在相同條件下於相同的電腦上執行，則我們似乎可以利用高階程式語言程式的執行時間與執行時所佔用的記憶體空間來衡量被實作演算法的效能。 不過，這太不實際了，而且藉由這個方式我們也難以直接看出演算法效能與演算法輸入規模(input size)的關係。 我們需要其他更具學理基礎，而且更容易分析與比較的方式來衡量演算法的效能

演算法的效能(續) 在學理上，我們使用: 來分析演算法的執行時間與佔用的記憶體空間。 時間複雜度(time complexity) 空間複雜度(space complexity) 來分析演算法的執行時間與佔用的記憶體空間。 以下我們先說明演算法的時間複雜度概念，而演算法空間複雜度則是類似的概念，我們在稍後演算法複雜度分析範例時會一併說明。

演算法的時間複雜度 演算法的時間複雜度分為以下三種狀況： 最佳狀況(best case)時間複雜度: 考慮演算法執行時所需要的最少執行步驟數。 最差狀況(worst case)時間複雜度: 考慮演算法執行時所需要的最多執行步驟數。 平均狀況(average case)時間複雜度: 考慮所有可能狀況下演算法執行時所需要的平均步驟數。 在上列的定義中，所謂的一個步驟(step)指的是演算法中的基本操作(operation)，如算術運算操作(arithmetic operation) 及邏輯運算操作(logic operation) 等。有時候我們也會將幾個連續執行的操作視為一個步驟，我們稍後會有詳細的說明。

演算法的時間複雜度(續) 在所有的時間複雜度之間，最差狀況時間複雜度是很重要的一項。 一般我們會先分析演算法的最差狀況時間複雜度，因為這項複雜度可以讓我們了解演算法在最壞的情況下的執行時間概況。 例如，假設我們需要使用一些天氣預測演算法來預測三天後的天氣慨況，並在一小時之後發佈預測結果。姑且不論演算法預測天氣的準確度，若我們能夠分析出這些演算法的最壞情況時間複雜度，則大約可以推估出哪些演算法即使在最壞情況下也可以在一小時之內執行完畢，讓我們來得及發佈天氣預測結果。

演算法的時間複雜度(續) 針對一些我們平日經常使用的演算法，會面臨各種不同狀況，執行步驟有時多有時少，而碰到最壞與最好狀況的機率又很低，則此演算法的平均狀況時間複雜度也很重要。 例如，我們經常使用排序(sorting)演算法將一連串的雜亂數字依由小到大的次序排好順序，或將一連串的雜亂檔案名稱依照字典順序(lexical order，如字典版將單字由A開頭排到Z開頭的順序)排列。因為可能面對不同的一連串數字與檔名，因而此時我們最關心排序演算法的平均時間複雜度。

演算法的時間複雜度(續) 相對於最差狀況時間複雜度與平均狀況時間複雜度，演算法的最佳狀況時間複雜度則顯得較不重要。 這是因為一方面最佳狀況出現的機率不高，而另一方面則是因為有時最佳狀況時間複雜度是顯而易見的(trivial)。 例如，我們直接利用質數(prime number or prime)的定義設計一個演算法，檢查一個輸入的大於2的正整數n是不是質數。依照定義，我們只要由整數2開始到n之間(不含n)找到任何一個n的因數(factor)，就可以判斷n不是質數了。對於這個演算法，若我們輸入任何大於2的偶數n，都可以馬上找出2是n的因數而判斷n不是質數，這對應演算法的最佳狀況時間複雜度，這顯然是顯而易見的。

演算法的時間複雜度(續) 一般而言，演算法的平均狀況時間複雜度最難分析(求出)，最壞狀況時間複雜度稍微容易些，而最佳狀況時間複雜度最容易分析。 我們通常會分析演算法的最壞狀況時間複雜度，若有可能，還會分析演算法的平均狀況時間複雜度，但是常常不分析最佳狀況時間複雜度。

演算法的時間複雜度(續) 一個檢查大於2正整數是否為質數的演算法

演算法的時間複雜度(續) 針對PrimeCheck1演算法，我們可以看出: 輸入大於2 的任意正整數n，若n 是質數，則演算法PrimeCheck1 需要執行整數除法求餘數(也就是n%i) 操作與整數比較(也就是(n%i)=0) 操作各n-2 次，才可以知道n 是質數。 另外，若n 不是質值，則演算法PrimeCheck1 只要執行整數除法求餘數操作與整數比較操作1 次就可以知道n 不是質數。 因此，我們很容易看出來，在最壞狀況下，演算法PrimeCheck1 的執行時間與輸入的正整數n 成正比；而在最佳狀況下，演算法PrimeCheck1 的執行時間大約為執行1次整數除法求餘數與整數比較操作，而與輸入的正整數n 大小無關。 也就是說，演算法PrimeCheck1 的最差狀況時間複雜度為n − 2，而演算法PrimeCheck1 的最佳狀況時間複雜度為1。 至於演算法PrimeCheck1 的平均狀況時間複雜度分析比較複雜，在此我們省略不提。

2. 大O漸近記號

漸近記號 一般我們使用漸近記號(asymptotic notation)表示演算法的複雜度(complexity)。 漸近記號考慮演算法在處理資料範圍或輸入規模(input size)或問題規模(problem size)足夠大時的複雜度。 使用漸近記號原因之一為聚焦於輸入規模足夠大的狀況: 一般而言，在演算法的輸入規模較小時，不管有效率(例如複雜度較低的PrimeTest1)或沒有效率(例如複雜度較高的PrimeTest2)的演算法通常都可以很快的執行完畢。相對的，在演算法的輸入規模非常大時，有效率的演算法還是可以在一定的時間內執行完畢，而沒有效率的演算法則可能需要相當長的時間，甚至於需要經年累月才能結束。因此，在分析演算法時，我們會聚焦於演算法輸入規模足夠大的狀況，這是為什麼分析演算法複雜度需要採取漸近記號的原因之一。

漸近記號(續) 使用漸近記號原因之二為簡化個別步驟認定: 當我們分析演算法時，認定不同的個別步驟經常會產生不同的時間複雜度。 例如，當我們將演算法PrimeCheck1中的整數除法求餘數操作與整數比較操作視為一個步驟時，我們說演算法PrimeCheck1的最差狀況時間複雜度為n-2。當我們將整數除法求餘數操作與整數比較操作視為二個個別步驟時，我們說演算法PrimeCheck1的最差狀況時間複雜度為2n-4。而當我們另外將迴圈控制中的迴圈變數遞增與迴圈變數與迴圈結束值的比較再視為另外二個個別步驟時，則我們可以說演算法PrimeCheck1的最差狀況時間複雜度為4n-8。 以上這些時間複雜度的說法，似乎都正確。當我們使用漸近記號來表示演算法複雜度的情況下，這些說法是完全相通的；更精確地說，它們使用漸近記號來表示時是完全相同的。這簡化個別步驟的認定，是我們使用漸近記號來表示演算法複雜度的原因之二。

漸近記號(續) 在演算法處理資料範圍或輸入規模足夠大時，演算法的執行時間複雜度會漸近於一個量級(order)。 一般而言，演算法的執行時間複雜度是一個輸入規模n的多項式，當演算法輸入規模足夠大時，時間複雜度多項式中除了最高次方的項目外，其他的部分都可以被忽略；而同時，最高次方項目的常數係數也同時可以被忽略。

漸近記號(續) 例如，若一個演算法的時間複雜度為n-2、2n-4或4n-8，則當n足夠大時，此演算法的時間複雜度漸近於n，屬於一次方或線性(linear)量級。 又例如，若一個演算法的時間複雜度為35n2+12n+11，則當n足夠大時，此演算法的時間複雜度漸近於n2，屬於平方(quadratic)量級。 而若一個演算法的時間複雜度為28n3+1245n2+162n+321，則當n足夠大時，此演算法的時間複雜度漸近於n3，屬於立方(cubic)量級。 一般而言，若是一個演算法的時間複雜度表示為一個多項式，則我們取這個多項式的最高次方為其時間複雜度的量級，並且將此量級以大O記號表示。以下我們詳細介紹大O記號。

大O記號 大O記號(Big-O notation)為一種漸近記號，我們通常使用大O記號來表示演算法在輸入規模足夠大時，其複雜度的量級漸近情形， 以下我們正式定義大O記號： [定義] 大O記號(Big-O notation): (O 代表order 之意) 令f(n) 與g(n) 是由非負整數對應至實數的函數，若存在正實數常數c 和正整數常數n0，使得對所有的n  n0 而言，f(n) ≤ cg(n) 成立，則我們說f(n) =O(g(n))。 因為O(g(n))帶有集合的涵義，因此f(n) =O(g(n))唸作「f(n) 屬於Big-O of g(n)」；而比較完整的英文唸法為「f of n is of Big-O of g of n」)。

大O記號(續) 例如，令f(n)=2n2 + n + 3 ，g(n) = n2。因為存在c = 6 和n0 = 1，使得當n  n0 = 1 時， f(n)= 2n2 + n + 3 ≤ cn2 = 6n2 =6g(n)成立，所以我們說f(n)=2n2 + n + 3 =O(g(n))=O(n2)。 我們可以由圖看出，當n  n0 = 1 時， f(n)  6g(n)成立，我們稱g(n)是f(n)的漸近上界(asymptotic upper bound)。這表示g(n)的成長率比f(n)還快或一樣快。

一些複雜度的大 O 記號表示及其量級

漸近上界 (Asymptotic Upper Bound)

漸近下界 (Asymptotic Lower Bound )

漸近緊界 (Asymptotic Tight Bound ) f(n) = (g(n))

漸近上界記號: Big O Def: f(n) = O(g(n)) “上限(upper bound)" iff  c, n0  |f(n)|  c|g(n)|  n  n0 e.g. f(n) = 3n2 + 2 g(n) = n2  n0=2, c=4  f(n) = O(n2) e.g. f(n) = n3 + n = O(n3) e.g. f(n) = 3n2 + 2 = O(n3) or O(n100 )

漸近下界記號: Big Omega Def : f(n) = (g(n)) “下限(lower bound)” iff  c, and n0,  |f(n)|  c|g(n)|  n  n0 e.g. f(n) = 3n2 + 2 = (n2) or  (n)

漸近緊界記號: Theta Def : f(n) = (g(n)) iff  c1, c2, and n0,  c1|g(n)|  |f(n)|  c2|g(n)|  n  n0 e.g. f(n) = 3n2 + 2 =  (n2)

漸近緊界定理 對任意兩函數f(n) 與 g(n), ⇔ &

3. 降低演算法時間複雜度量級

演算法時間複雜度量級比較 我們首先比較不同演算法時間複雜度在各種不同量級之下的執行步驟數。 某些量級在演算法的輸入規模還不是很大的情況下，演算法時間複雜度的對照數值(執行步驟數)就已經相當大了，這表示演算法需要執行相當久的時間。 例如，若演算法的一個步驟(如比較兩個整數的操作)需要一個微秒(s, micro second，百萬分之一秒)來完成，則當輸入規模n 為32 時，平方量級演算法需要1,024 微秒≈0.001 秒來完成，而指數量級演算法需要2n=4,294,967,296 微秒≈143 分鐘來完成。

演算法時間複雜度量級比較(續) 演算法時間複雜度量級高低的次序 (靠左邊的量級是比較低，成長比較慢的量級)： O(1)，O(log n)，O(√n)，O(n)，O(n log n)，O(n2)，O(n3)，O(2n) 設計一個時間複雜度量級比較低的演算法是我們必須一直擺在心中的目標。

測試質數的一個觀察 以下，我們再舉檢查一個正整數是否為質數的演算法為例，來看看是否能夠設計出時間複雜度更低的演算法。 我們有以下的觀察: [觀察] 對於任意的大於2 的整數n 而言，若所有小於或等於 √n 的整數(1 除外)都無法整除n，則n 是一個質數。

觀察實例 每個整數n的因數都是成對出現的，例如，16的因數為1與16(116=16)、2與8(28=16)、4與4(44=16)。成對出現的因數中，一個會小於等於n的平方根，而另一個則是大於等於n的平方根，因此，我們只要檢查小於等於n的平方根的所有不等於1的整數中是否有n的因數就可以知道n是不是質數了。

另一個用以測試質數的演算法 我們根據上列觀察設計出另一個演算法PrimeCheck2

以Java程式語言實作 PrimeCheck1演算法 下列的Java語言程式PrimeCheck1.java實作PrimeCheck1演算法，並使用System.currentTimeMillis()測量程式執行時間:

PrimeCheck1.java執行結果

以Java程式語言實作 PrimeCheck2演算法 下列的Java語言程式PrimeCheck2.java實作PrimeCheck2演算法，並使用System.currentTimeMillis()測量程式執行時間: :

PrimeCheck2.java執行結果

質數檢查演算法時間複雜度比較 最差狀況(worst case)時間複雜度: 最佳狀況(best case)時間複雜度: PrimeCheck1: n-2 PrimeCheck2: √n − 1 最佳狀況(best case)時間複雜度: PrimeCheck1: 1 PrimeCheck2: 1 當演算法的輸入規模n越大時，演算法PrimeCheck1與演算法PrimeCheck2在最差狀況下的執行步驟數差距越大。例如，當n=65537時，演算法PrimeCheck1需要執行n-2=65536次整數除法求餘數和整數比較敘述才可以得知65537是質數，而演算法PrimeCheck2只要執行√n-1= 255次，二者的差距約為√n=256 倍。而當n=2147483647，則演算法PrimeCheck1 需要執行n-2=2147483645次整數除法求餘數和整數比較敘述才可以得知2147483647是質數，而演算法PrimeCheck2只要執行√n-1= 46339次，二者的差距約為√n=46340 倍。

質數檢查演算法複雜度量級比較 最差狀況(worst case)時間複雜度: 最佳狀況(best case)時間複雜度: PrimeCheck1: n-2=O(n)，屬於線性量級。 PrimeCheck2: √n − 1 =O(√n)，屬於平方根量級。 最佳狀況(best case)時間複雜度: PrimeCheck1: 1=O(1)，屬於常數量級。 PrimeCheck2: 1=O(1)，屬於常數量級。 在最差狀況下，平方根量級的演算法PrimeCheck2的執行步驟數將比線性量級的演算法PrimeCheck1的執行步驟數少很多。例如，若輸入的n 為2147483647，則演算法PrimeCheck1 需要執行n-2=2147483645次整數除法求餘數和整數比較敘述才可以得知2147483647是質數，而演算法PrimeCheck2只要執行√n-1= 46339次，二者的差距約為√n=46340 倍。當然，當所輸入的n越大時，這種差距越大。

4. 多項式時間、指數時間及 偽多項式時間演算法

多項式時間演算法 若一個演算法的時間複雜度為多項式函數，則其為 範例: 費伯納西數列演算法 多項式時間複雜度演算法(polynomial time-complexity algorithm) 多項式時間演算法(polynomial time algorithm) 多項式演算法(polynomial algorithm) 範例: 費伯納西數列演算法

指數時間演算法 若一個演算法的時間複雜度為指數函數，則其為 範例: 遞迴費伯納西數列演算法 指數時間複雜度演算法(exponential time-complexity algorithm) 指數時間演算法(exponential time algorithm) 指數演算法(exponential algorithm) 範例: 遞迴費伯納西數列演算法

偽多項式時間演算法 若一個演算法的時間複雜度為輸入數值(numeric value)的多項式函數，但是卻是輸入長度(用以表達輸入的位元數)的指數函數，則其為 偽多項式時間複雜度演算法(pseudo-polynomial time-complexity algorithm) 偽多項式時間演算法(pseudo-polynomial time algorithm) 偽多項式演算法(pseudo-polynomial algorithm) 範例: PrimeCheck1 and PrimeCheck2演算法

費伯納西數列 費伯納西數(Fibonacci series)定義: F1 = F2 = 1 Fn = Fn-1 + Fn-2 1, 1, 2, 3, 5, 8, 13, 21, 34, …

費伯納西數列演算法 Algorithm Fibonacci(n) Input: 正整數n Output: 費伯納西數列第n項 if (n=1 or n=2) then return 1 else a1;b1 for i3 to n do ca+b ab bc end for return c end if Time Complexity: O(n)

遞迴費伯納西數列演算法 Algorithm RecursiveFibonacci(n) Input: 正整數n Output: 費伯納西數列第n項 if (n=1 or n=2) then return 1 else a  RecursiveFibonacci(n-1) b  RecursiveFibonacci(n-2) return a+b end if Time Complexity: O(2n)

遞迴費伯納西數列演算法 時間複雜度分析 假設遞迴費伯納西數列演算法的時間複雜度為T(n)，則我們有: T(1)=T(2)=1 T(n)=T(n-1)+T(n-2)+12T(n-1)+1 =2(2T(n-2)+1)+1 =4(2T(n-3)+1)+1+2=… =2kT(n-k)+(1+2+…+2k-1)= 2kT(n-k)+(2k-1) 令n-k=1，則代入k=n-1，我們可得 T(n)  2n-1+(2n-1-1)  2n for n3 因此，T(n) = O(2n)

5. 演算法複雜度分析範例一

演算法複雜度分析範例 在本單元中，我們以氣泡排序(bubble sort)與插入排序(insertion sort)演算法為例，再一次演示演算法的複雜度分析。 所謂排序(sorting)是將一系列的元素(資料)依照某種順序排列的程序。例如，若元素為數值，則排序將依元素數值的大小以由小而大或由大而小的數值順序(numerical order)排列；又例如，若元素為字串，則排序將依字串的字典順序(lexical order)排列。 在本單元中，我們針對一個元素為數值的陣列，說明氣泡排序與插入排序演算法如何將陣列元素依由小而大的數值順序排列。然後我們針對這二個演算法的時間複雜度、空間複雜度進行分析與比較。

氣泡排序演算法 氣泡排序(bubble sort)演算法又稱為下沉(sinking)排序演算法或交換(exchange)排序演算法。 因為它的執行步驟中每回合(pass)會找出目前未處理過資料中最大的一個，就如同讓最大的氣泡先由水中冒出，然後再讓第二大的氣泡冒出，...，因此稱為氣泡排序演算法。 因為它在執行步驟中，如同每回合會讓最重的東西往下沉，然後再讓第二重的東西往下沉，...，因此稱為下沉排序演算法。 因為它的執行步驟為不斷的比較並交換兩個相鄰的資料，因此又稱為交換排序演算法。

氣泡排序演算法(續) 假設我們現在要使用氣泡排序演算法來將陣列中的n 個元素或資料(索引為0,...,n − 1)依照其值以由小而大的次序排列 其做法為持續兩兩比較相鄰資料，若前一筆(左邊)資料的值大於後一筆(右邊) 資料的值，則將此二筆資料互相交換，否則資料的位置即維持不動。上述的比較及交換過程一直持續進行到最後一筆資料被比對到為止，這稱為一個回合(pass)。 第一個回合的比對進行到最後一筆資料為止(n − 1 次比對)，此時具最大值的資料已經調換至最後(最右邊) 的位置了；而第二回合的比對則進行到倒數第二筆資料為止，此時具第二大值的資料已經調換至倒數第二個位置了； … ；其餘依此類推。當進行完第n − 1 個回合(比較索引為0 與1 的資料) 之後，則所有的資料均已依由小到大的次序排列好了。

氣泡排序演算法(續)

氣泡排序演算法(續) 我們舉以下的實例來看看氣泡排序的運作情形： 假設有一個陣列具有 5 個元素 8、5、8’、6、7，索引為 0,...,4，其中 8 與 8’二個元素的值都是 8，但是為了區別起見，我們將之標示為 8 與 8’。 此陣列經由氣泡排序法排序的過程如下頁圖所示。其中加垂直線的方格代表索引變數 i 所指的元素，而加水平線的方格代表索引變數 j 所指的元素。

氣泡排序演算法(續)

氣泡排序演算法(續) 在整個氣泡排序演算法的過程中，8與8’的相對位置一直保持不變，也就是8一直排列在8’之前。 當一個排序演算法能夠讓具有相同值的元素維持原來的相對位置時，我們稱這種排序演算法為穩定(stable)排序演算法。 若我們所排序的元素只是一個資料庫的鍵值(key)，則穩定排序演算法在排序之後可以保持所有紀錄原來的次序，這是非常有用的功能。 例如，我們可以先針對學生成績資料庫先依國文成績由高到低排序，之後再依總成績由高到低排序。此時資料庫資料的排列次序為總分高的在前，而總分相同的則由國文成績高的排在前面。

氣泡排序演算法(續) 除了幾個索引變數之外，氣泡排序演算法不需要額外的記憶體空間來輔助排序的進行。 不需要額外記憶體空間的排序演算法稱為就地(in place) 演算法。 這也是很好的特定，這表示氣泡排序演算法的空間複雜度可以視為是常數的(也就是O(1))，而與所需要排序的陣列的大小無關。

氣泡排序演算法(續)  

6. 演算法複雜度分析範例二

插入排序演算法 以下我們介紹插入排序(insertion sort)演算法。 假設我們想要使用插入排序演算法將一個陣列中的元素依照其值由小而大排列，其做法是從第二個元素開始，先以其為處理對象，並向前比對每一個元素以找出其適當插入位置；然後以第三個元素為處理對象，並向前比對每一個元素以找出其適當插入位置，...。 這類似我們在交考卷時的一種排序概念：每位學生寫完考卷時就交上自己的考卷；而老師為了方便讓考卷依座號的次序由小到大排序，在每個學生交上考卷時即在已經交上的考卷中從頭到尾(或從尾到頭)找出新交考卷的適當位置插入。 在老師手上的考卷永遠都是依座號的次序由小到大排列，而當所有學生都交出考卷時，所有的考卷就已經依座號的次序由小到大排序完畢了。

插入排序演算法(續) 以下為插入排序(insertion sort)演算法。

插入排序演算法(續) 我們舉以下的實例來看插入排序演算法的運作過程： 假設有一個陣列具有5個元素8、5、8’、6、7，索引(index)為0,...,4，其中8與8’二個元素的值都是8，但是為了區別起見，我們將之標示為8與8’。 此陣列經由插入排序演算法排序的過程如下頁之圖所示

插入排序演算法(續)

插入排序演算法(續) 在整個插入排序演算法的執行過程中，8 與 8’的相對位置一直保持不變，因此插入排序演算法也是一個穩定(stable)排序演算法。 除了幾個索引變數與一個陣列數值臨時儲存變數之外，插入排序演算法不需要額外的記憶體空間來輔助排序的進行，因此插入排序演算法也是一個就地 (in place) 演算法，其空間複雜度為 O(1)。

插入排序演算法(續)  

插入排序演算法(續) 資料已經由小到大排好的情況下為最佳狀況，在這種情況下，所有的mi=0 (1 ≤ i ≤ n−1)，因此我們有M = 2(n−1) = 2n−2 =O(n)。 當資料為反向的由大到小排列時為最差狀況，在這種情況下，m1= 1;m2= 2; …;mn-1 = n − 1，或者我們寫為mi = i (1 ≤ i ≤ n − 1)，因此我們有M = n(n-1)/2+2(n − 1)=O(n2)。

插入排序演算法(續)  

氣泡排序與插入排序演算法比較

The End

補充: 有關大O記號 以下我們正式定義大O記號： [定義] 大O記號 (Big-O notation) 令f(n)與g(n)是由非負整數對應至非負實數的函數，若存在正實數常數c>0和正整數常數n0使得對所有的nn0而言，f(n)cg(n)成立，則我們說f(n)=O(g(n))。(唸作 「f(n)是屬於Big-O of g(n)」，比較正式的英文唸法為「f of n is of Big-O of g of n」)。 例如，針對35n2+12n+11而言，存在c=58和n0=1(58由35+12+11求得)，使得當nn0=1時，35n2+12n+11cn2=(58n2)成立，因此，我們說35n2+12n+11=O(n2)。