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

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

前言

第一天我們針對了演算法做了非常簡單的介紹，我們提到演算法本身是一個用來解決問題的一系列精準不模糊的步驟或指示，而食譜中的製作步驟可以說是生活中的演算法，因為它很明確地告訴了讀者每一個步驟要如何進行、每一個環節要如何處理；再來我們用了如何求出兩個數值的最大公因數來解釋一個數學層面的演算法，同時舉出了兩種不同的演算法來解決這個問題。如果還沒看過或已經忘記第一天的內容，可以點擊這裏複習一下。

我們上次提到解決最大公因數的問題時有兩種演算法，而這兩種演算法有效率上的差異，那這個效率一定要把演算法實作出來後，實際上去執行計算時間才有辦法知道嗎？還是有什麼辦法可以在設計的時候就可以估算、評估的呢？

今天，我們將會介紹如何解析一個演算法的優劣。

演算法優劣的衡量因素？

一個演算法的好壞可以從兩個因素去衡量：執行時間(time complexity)、使用空間(space complexity)。前者也稱作效能或效率，對於要處理的資料量不大的狀況下，演算法的效能問題基本上無感，然而一但資料量倍增，這個問題就會變成誰也無法忽視的難題。演算法的效能直接影響了系統執行的速度，間接影響了使用者的使用體驗，進而影響了公司的基礎運作，以購物網站為例，成千上萬種商品，假如你想要搜尋某一個關鍵字的產品，網頁遲遲不出搜尋結果，那你可能也不會想繼續等了，之後你應該也不會再使用這個購物平台了，如此一來，這個網站的使用率直線下滑，經營的公司估計也可以打包收掉了。後者指的是一個演算法在執行過程中使用的儲存空間(如：Memory space)，基本上每一台機器的硬體設備是有限的，當一個程式在執行的時候，它所使用的Memory也不會無限上綱，而如果演算法在執行的過程中直接忽略了使用空間的問題，可能執行到中途就會出現記憶體不足的問題，這樣程式就沒辦法正常執行了。

這次的30天系列文中，主要是針對演算法執行時間(time complexity) 來進行討論。

如何去估計演算法的效率？

要估計演算法的效率，首先我們要先知道兩個名詞定義：

1. Basic Operation:

Basic operation的定義是指在整體演算法執行『一次』的過程中，進行最多次的操作，白話一點就是『跑一次，什麼動作做了最多次』，如：加減乘除、等於、比較等。

2. Input Size:

Input Size的定義就是這個『需要被解決的問題的大小（資料量）』，如：若要從一個長度為n的陣列中搜尋一個指定的物件，那這個陣列的長度n就是input size。

舉一個非常簡單的範例–計算次方–來解釋：

// Input: number, times
// Output: number^times
public Integer square(Integer number, Integer times){
    int result = 1;
    for (int i = 1 ; i <= times ; i++){
        result = result * number;
    }
    return result;
}

範例中的Basic Operation就是『乘(＊)』，因為這個演算法在執行過程中，主要是在進行『乘』的這個動作；而迴圈執行的次數取決於times，因此times即為Input size。

那既然我們知道了這兩個名詞分別代表的意義之後，又要怎麼去估計理論上的效率呢？

應該已經有人想到了吧，執行時間 ≈ 一次的動作時間 × 動作次數，因而有了下列公式：

t(n) ≈ Cop × C(n)

• n : Input size
• t(n): 執行時間
• Cop : 單一次basic operation執行的時間
• C(n) : basic operation執行的次數

以上面計算次方的範例來說，n是times，而因為演算法每執行一次，『相乘』的動作也只執行一次，因此C(n)為1 x times = times，另外我們假設『乘』每執行一次所需要的時間為Cop，所以計算公式為 ➜ 執行時間t(n) ≈ Cop × C(n) ≈ Cop x times。

讓我們再舉一個例子讓大家更熟悉一點：依序尋找Array中某一個值的index

// 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;
}

這個範例中，會從array的第一個element依序地開始尋找target，找到target後就回傳當下的index，對於這個範例的Basic operation、Input size、Time complexity分別是：

• Basic operation: 加(+)、等於(=)、比較（<, !=)
• Input size: array的長度(array.length)
• Time complexity: t(n) ≈ Cop × C(n) ≈ Cop x array.length, as C(n) = 1 x array.length

註：

1. Basic operation中的『等於』，是賦值的意思
2. Time complexity中，我們假設單一次basic operation執行的時間為Cop

如果有人腦筋動比較快可能會想到：『那如果Array的第一個element就是target和最後一個element才是target，這樣兩種情況就是不一樣的，執行時間也是不一樣的才對！』，沒錯，但如果今天在介紹下去，估計內容就太多了，可能會有點難以消化，因此我們明天再繼續解析演算法的優劣下集。

小結

1. 名詞解釋：
   

   名稱	解釋
   Basic Operation	在整體演算法執行『一次』的過程中，什麼事情做了最多次
   Input size	演算法總共執行了幾次

2. 衡量一個演算法好壞的因素有二：

   • 執行時間(Time complexity)
   • 使用空間(Space complexity)

3. 估算演算法的執行時間：t(n) ≈ Cop × C(n)

預告

下一篇將會繼續說明如何解析一個演算法的優劣。

References

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

• ← 【舌尖上的演算法】Day1 -- 初嚐演算法
• → 【舌尖上的演算法】Day3 -- 解析演算法的優劣（下）