<aside>

### 演算法的簡單定義式：輸入 + 演算法 = 輸出

<aside>

演算法用最直白的方式來說，就是我輸入一個東西，想要得到另外一個東西，
經過的過程就是所謂的演算法。
假設我們輸入一個 2 還有一個 3，如果想要得到 6，
我們需要在中間加上一個演算法「乘號 X」，讓 2 x 3 = 6。

又例如，我今天輸入一顆橘子，想要得到一杯橘子汁，中間可能經過果汁機，
或是經過憤怒的手。只要最後可以順利得到橘子汁，
中間的過程就可以稱為它的演算法。


</aside>

</aside>

<aside>

## **複雜一點的演算法**

而實際上，演算法可能複雜得多，就像假設我們今天不只要做一杯橘子汁，
而是要煮一碗洋蔥燉湯，我們輸入洋蔥、油、水、鹽，想要得到洋蔥燉湯，
這碗燉湯的演算法可能會類似於 :
1. 鍋中倒入一匙油2. 熱油3. 把洋蔥切末
4. 洋蔥炒至金黃色後加入一鍋水5. 加一些鹽熬煮 10 分鐘

在日常生活中，像這樣的演算法可說是隨處可見。
而在文章一開始提到，我們在接觸程式時常聽到「演算法」的這個詞，
通常是指把這些步驟具體寫成程式，用來達成特定目的的過程。
這些演算法簡單的可能像是把一堆[數字排序](https://www.youtube.com/watch?v=kPRA0W1kECg)，
複雜的可能如大家每天用的 Facebook 所用不斷更新的 [News feed 演算法](https://techcrunch.com/2016/09/06/ultimate-guide-to-the-news-feed/)。

在認識了演算法基本的定義後，接下來，
就讓我們進一步來認識評斷一個演算法好壞的工具：`時間複雜度` (Time Complexity)。

</aside>

<aside>

## 時間複雜度
BigO代表的是「演算法執行步驟數目上限」

要判斷一個演算法的好壞，最基本的兩個指標是 :
<font color="#f00">
- 這個演算法有多快
- 需要用到的記憶體有多少
</font>

因為時間與空間的概念大致上是互通的，我們就先來瞭解比較常見的時間複雜度。

時間複雜度是用來評斷演算法執行快慢的指標，
而實務上我們通常用Big O符號（Big O notation）來記錄時間複雜度的快慢。
接下來，先讓我們用一個簡單的例子來認識什麼是Big O符號吧！

</aside>

<aside>

## **模擬看電影跟Big**O**符號的關係**

假設你今天心血來潮，想要重看經典電影名著《鐵達尼號》。你有兩個方法：
(1) 走到離你家最近的租片店，租片來回需要花 25 分鐘。
(2) 從網路上下載檔案，一部需要花 20 分鐘。
兩者花的時間差距不大，但你可能會先選擇從網路下載。

現在，讓我們重新假設。你今天心血來潮，不只想要看《鐵達尼號》，
也想要順便複習《哈利波特》全集＋《魔戒》三部曲。
此時，去租片店拿到這一拖拉庫的電影還是只需要花走路的時間 25 分鐘，
但從網路下載，你卻需要等電腦下載 4 個小時，這時，你可能不會選擇從網路下載。


在上面的例子中，如果選擇去**租片**店取得電影，
所要取得的時間**不受**想要看的電影部數影響。
`也就是你的腦袋不管輸入幾個電影需求（Input），
最後得到電影（Output）的時間都不會因此增加。`
這樣的特性，如果我們想要用Big O 符號去表示這次租片的演算法，
我們會把演算法的時間複雜度（常以 T(n) 代表）記為 **O(1)**。

而如果選擇從網路上下載電影，
很明顯的你`輸入 n 個電影需求，拿到電影的時間就會隨著 n 成倍數成長`。
此時，我們會用Big O 符號把 T(n) 記為 **O(n)**。

看到這裡，我們可以對時間複雜度有一個最基礎的認知，也就是：

<aside>
💡 Big O 符號是用來描述一個演算法在輸入 n 個東西時，
執行所花費的總時間與 n 的關係。

</aside>

</aside>

<aside>

## **常見的時間複雜度比較**

在設計一個程式演算法時，我們會Big O 符號比較演算法執行的效率好不好。而通常，我們會希望一個演算法至少能比 O(n²) 還要快，如果能到 O(n)、O(1) 甚至是 O(log n) 的話是最理想的情況。

從下面這張圖我們可以看到，當時間複雜度為 O(n²) 時，只要輸入的個數增加一些，它所需要花的時間就會大幅度的增加。想像一下當 n = 10,000 時，O(n²) 所需要花費的時間就會比 O(n) 的時間多一萬倍。因此，在處理大量的資料或複雜運算時，一個好的演算法設計可以省下的時間是很可觀的。


</aside>

<aside>

## **進階篇：深入時間複雜度的實際情況**

到目前為止，我們認識了何謂演算法，以及評斷演算法設計好壞的工具：時間複雜度。

細心的人可能會好奇，為何上面比較圖的縱軸項目是步驟數而不是執行時間呢？

首先，我們要先來小小定義一下在程式設計中的「步驟次數」是指什麼。
通常在程式碼中，每個動作只要被執行一次，我們就會說他是一個步驟，
而這些動作包含印出、賦值、陣列讀取等等。

舉例來說，在程式碼中我們宣告：

賦予變數 x 數值 10 的這個動作就是一個步驟。

int x = 10;

再舉另外一個例子：

在 for 後面的迴圈中，輸出”你好！”這個動作被執行從 x = 1 到 x = 10 總共 10 次，
因此這個 for 迴圈總共的步驟次數就是 10。
但也別忘了，int x = 10 也是一個步驟，
所以下面的程式碼總共的步驟次數 = 11。

public class Main {
    public static void main(String[] args) {
        // 第一個步驟：設定 x
        int x = 10;
        
        // for迴圈執行10次
        for (int i = 1; i <= x; i++) {
            System.out.println("你好！");
        }
    }
}    

</aside>

<aside>

### 演算法有多快不是以秒衡量，而是以步驟次數來看

前面看電影的例子為了方便釐清Big O 符號跟輸入 n 的關係，我們用時間來舉例，
但實際上，我們要真正衡量演算法時，是以步驟次數來看。

為何看演算法有多快不是用執行時間要幾秒呢？
想像一下，美國 NASA 超級電腦需要執行 1 秒的程式，
拿到我們家裡電腦執行可能需要 100 秒。
而同樣的程式，用 C 語言寫跟用 Python 寫也跑的不一樣快。
因為電腦效能和語言特性的都會造成影響，
因此用執行時間來衡量演算法的快慢顯然不是個穩定的指標。

回過頭來使用上面看電影的例子，
假設取得電影的動作我們可以用一個「只要一個步驟」的函式 get_movie( ) 替代，
則「想看十部電影之走路方案」的程式碼就是單純的 :

public class WalkingPlan {
    public static void main(String[] args) {
        // 想看十部電影之走路方案：步驟次數 = 1 次
        int n = 10;
        getMovies(n);
    }
    
    public static void getMovies(int count) {
        System.out.println("一次取得 " + count + " 部電影");
    }
}

而「想看十部電影之下載方案」的程式碼可以寫成 :

public class DownloadPlan {
    public static void main(String[] args) {
        // 想看十部電影之下載方案：步驟次數 = 10 次
        int n = 10;
        
        for (int i = 1; i <= n; i++) {
            getMovie();
        }
    }
    
    public static void getMovie() {
        System.out.println("下載一部電影");
    }
}      

我們從上面兩段程式碼可以觀察，
- 走路方案是 O(1) 的時間複雜度
- 下載方案是 O(n) 的時間複雜度

所謂「步驟次數」通常會以一段程式碼中迴圈執行的次數決定（先不考慮遞迴）。

假如今天是 <font color="#f00"> 從 1 迭代到 n 的迴圈，代表步驟次數 n。 </font>

同樣的<font color="#f00"> 如果是一個 n 迴圈裡面再包一個 n 迴圈，
代表他的步驟次數就是 n²。 </font>

而如果整段程式碼都<font color="#f00">沒有用到迴圈或遞迴，則步驟次數通常以 1 表示。</font>

</aside>

<aside>

## **實務上我們如何記錄時間複雜度**

那如果一個程式中有好幾個迴圈，有單純的迴圈也有雙重迴圈，
這樣的步驟次數換成BigO 符號要怎麼表示呢？
讓我們從下面的程式碼來瞧瞧：

public class TimeComplexityExample {
    public static void main(String[] args) {
        int n = 10; // 假設 n = 10
        
        // 第一段：O(n) 的迴圈，步驟次數 = n
        for (int i = 1; i <= n; i++) {
            getMovie();
        }
        
        // 第二段：O(n²) 的迴圈，步驟次數 = n²
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                getMovie();
            }
        }
        
        // 第三段：O(n²) 的迴圈，步驟次數 = n²
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                getMovie();
            }
        }
        
        // 總步驟次數 = n + n² + n² = 2n² + n
        // 但依據 Big O 表示法的化簡原則：
        // 1. 只保留最高次方項
        // 2. 省略所有係數
        // 因此最終的時間複雜度為 O(n²)
    }
    
    public static void getMovie() {
        System.out.println("取得一部電影");
    }
}  

1. 第一個迴圈：
- 只有一層迴圈
- 執行 n 次
- 貢獻了 n 步驟
2. 第二個迴圈：
- 兩層巢狀迴圈
- 執行 n × n = n² 次
- 貢獻了 n² 步驟
3. 第三個迴圈：
- 也是兩層巢狀迴圈
- 同樣執行 n × n = n² 次
- 貢獻了 n² 步驟

總步驟數：

- 數學表示：2n² + n
- Big O 表示：O(n²)

這是因為：

1. n² 是最高次方項
2. Big O 符號會省略常數（2）
3. Big O 符號只保留最高次方項（捨棄 n）

所以即使實際步驟數是 2n² + n，
我們仍然用 O(n²) 來表示這個程式的時間複雜度。
這種表示方法讓我們能夠快速理解程式在處理大量資料時的效能表現。

實務上，當我們要將步驟次數轉換成以BigO 符號紀錄的時間複雜度時，
有一個很重要的原則，也就是要「盡可能化簡」。

數學上，在 n 相當相當大的時候，
我們在比較兩個數的大小時可以只比較他們的最高次方。
因此在記錄時間複雜度時，我們同樣地會只記錄最高次方的那一項。

另外，為了方便記錄，我們也會省略所有係數，
讓時間複雜度的記錄可以符合「盡可能化簡」的原則。
也因此，上面有 2n² + n 個步驟的程式，我們會把它的時間複雜度簡單記成 O(n²)。

那如果是 2n² + n 個步驟的的跟兩倍步驟數 4n² + 2n 呢?
答案是時間複雜度一樣是 O(n²) 。
我們可以把BigO 符號想像成一個區段類別，而不是一個非常非常精確的記錄單位。
因此所有落在最大係數 n² 這個區段的步驟數，我們就會全部將它們歸在 O(n²) 囉！

</aside>

<aside>

# **結論**

1. 演算法的簡單定義：輸入 +演算法 = 輸出
2. 時間複雜度：衡量演算法執行好壞的工具
3. Big O符號：用來描述演算法在輸入 n 個東西時，總執行時間與 n 的關係
4. 在 n 非常大時，好的演算法設計可以省下非常多時間
5. 演算法的速度不是以秒計算，而是以步驟次數
6. 實務上，我們只會紀錄最高次方的那一項，並忽略其所有的係數

- 文獻參考

[https://medium.com/appworks-school/初學者學演算法-談什麼是演算法和時間複雜度-b1f6908e4b80](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AB%87%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95%E5%92%8C%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-b1f6908e4b80)
</aside>