【舌尖上的演算法】Day3 -- 解析演算法的優劣（下）

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

第二天我們提到了衡量一個演算法好壞的因素分別是執行時間(Time complexity)和使用空間(Space complexity)，而估算演算法的執行時間的公式是t(n) ≈ Cop × C(n)，也提出了一個很簡單依序尋找Array中某一個值的index的例子，自然應該就會有人想到目標若在Array中的位置不同，結果就會不同，今天我們將會接續這個議題進行說明。

// array = [A1, A2, A3, ..., An]
public Integer sequentialSearch(Integer[] array, Integer target){
    Integer index = 0;
    while ( index < array.length && array[index] != target){
        index = index + 1;
    }
    return index;
}

三大名詞

1. Best Case：

Best case指的就是一個演算法執行時『最好的情況』，以這個sequentialSearch為例，最好的情況就是第一個element就是target，所以這個時候執行的次數就是1；而Time complexity則是t(n) = Cop。

2. Average Case：

Average case指的是一個演算法執行的『平均』遇到的情況，基本上就是一個平均值。而要去探討一個Average case最難的就是要去考慮到所有的可能性，同樣以sequentialSearch為例，要去考慮target可能在每一個element中找到，換言之，所有可能性的執行次數的平均值為C(n) = (1+2+3+4+...+n)÷n ，這時Time complexity則是t(n) = Cop x ((1+2+3+4+...+n)÷n)。

3. Worst Case：

Worst case就是一個演算法執行時『最差的情況』，再以sequentialSearch為例，最差的情況就是target在這array中找不到或在最後一個element才找到；因為每執行一次sequentialSearch，進行一次『比較』的動作，因此這時執行的次數就是array的長度array.length，Time complexity則是t(n) = Cop x array.length。

通常我們在討論一個演算法的效率問題時，不太常去針對Average case進行探討或比較，原因就如同剛剛有提到的，若要探討Average case，需要考慮到所有的可能性，然而實際上，真的很難考慮到所有的情況，因此在接下來的文章中，我們針對演算法的time complexity也會著重在Best case和Worst case上。

如何比較數個演算法的優劣？

假設現在上面兩個範例計算次方和依序尋找的Cop分別是5.1和5.2，而C(n)都是n，這樣的話兩者的Time complexity分別是：

• 計算次方： T1(n) = 5.1n
• 依序尋找： T2(n) = 5.2n

而這兩個方程式轉換成2D線性圖時，看起來幾乎沒有差異：

那假設C(n)改為n的2次方，那線性圖則會變成下圖，同樣看起來也幾乎沒有差異：

從上面兩個圖可以知道，在這個方程式中，當n的值越大，真正影響曲線結果的是basic operation執行的次數-C(n)，Cop反而不那麼重要，也就是說，我們在比較演算法的執行效率時，最主要是針對C(n)來進行討論，而在數學當中，我們會用 Big O Notation (𝜪) 來表示一個演算法簡化後的Time complexity。

Big O Notation是用一個更簡單的函數來表達一個方程式（函數）的漸進上界(註1）；假設現在有一個方程式為2n^3 + n^2 + 10，當n越來越接近∞時，2n^3會慢慢地佔據了這個方程式整體走向的主導地位，進而使方程式中的其他部位可以被忽略，有了簡化之後的結果，而因為在比較演算法效率時，n的值基本上都會被視為∞，因此Big O notation非常適合用來分析演算法的time complexity。

註1：漸進上界指的是接近無窮級數時的狀態。

以T1(n) = 5.1n為例，我們可以說T1(n) ∈ 𝜪(n)(註2）；若C(n)改為n的2次方T1(n) = 5.1n^2，那就是T1(n) ∈ 𝜪(n^2)。透過Big O Notation，我們就可以忽略方程式中比較不重要的『常數』(Cop)，專注在實際上會影響執行時間的參數(C(n))，進而比較不同的演算法的效率，以前面提到的兩個Big O notation來比較效率的話，𝜪(n) > 𝜪(n^2)。

註2：∈是『屬於』的意思，按照上面的例子來說，就表示T1(n) = 5.1n 這個方程式是屬於𝜪(n)的一種。

下圖是在分析演算法的效率時常用到的Time complexity（來源:Time Complexity-Wikipedia)，從圖中我們可以知道，在Big O Notation的考量下(n ≈ ∞)，主導執行時間(N)的最主要因子是方程式中與n有關最大的參數（以2n^3 + n^2 + 10為例，與n有關最大的參數即為2n^3）。

小結

1. 名詞解釋：
   

   名稱	解釋
   Best case	一個演算法會遇到的最好情況的結果
   Average case	一個演算法會遇到的平均情況下的結果
   Worst case	一個演算法會遇到的最差情況的結果

2. Big O Notation (𝜪) 的概念在電腦科學上常用來分析演算法的Time complexity。

3. 若有一個演算法的Time complexity方程式為2n^3 + n^2 + 10，在Big O notation的概念中，當n ≈ ∞時，2n^3會成為主導一個演算法執行時間最主要的因素。

預告

下一篇將會介紹8種不同的資料型別及其特性。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin
2. Big O notation - Wikipedia
3. Time complexity - Wikipedia

• ← 【舌尖上的演算法】Day2 -- 解析演算法的優劣（上）
• → 【舌尖上的演算法】Day4 -- 抽象資料型別及特性