這次一路學了 Bubble Sort、Quick Sort、Dijkstra，也真的把它們做成視覺化動畫。

所以最後一天，我想回到前面曾經學過的 Big O，重新看看這三種演算法到底差在哪裡。

還記得 Day 4 學 Big O 時，有提到一個很重要的概念：

「演算法有多快不是以秒衡量，而是以步驟次數。」
這句話引用自 AppWorks School－初學者學演算法：談什麼是演算法和時間複雜度。

這次不比較三種演算法實際跑了幾秒，而是重新看看：當資料量增加時，它們需要處理的步驟會怎麼變化？

Bubble Sort：資料越多，要比較的次數也越多

Bubble Sort 的核心流程很單純：

兩兩比較 → 必要時交換 → 重複下一輪。

假設 Array 有 n = 8 筆資料，第一輪比較 7 次、第二輪 6 次……最後加起來：

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28

當 n 越來越大，比較次數會呈現平方等級的成長，因此一般 Bubble Sort 的平均與最差時間複雜度是：

O(n²)

這裡的 Bubble Sort 複雜度整理參考自 Ralph Tech〈演算法學習筆記－氣泡排序〉。

Quick Sort：為什麼同樣排序，通常比較快？

Quick Sort 不會像 Bubble Sort 一樣不斷進行相鄰比較，而是：

選 Pivot → Partition → 左右繼續切分。

例如有 8 筆資料，如果每次 Pivot 都能把資料切得比較平均，可以先用對半分的方式理解切分層數：

12345678
↓ 第一層：分成兩組
1234 | 5678

↓ 第二層：每組繼續對半分
12 | 34 | 56 | 78

↓ 第三層：每組剩下一筆
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

這只是方便理解層數的示意圖；實際 Quick Sort 每次 Partition 還會選出一個 Pivot。

這裡的 log n 可以先簡單理解成：資料不斷對半切，直到剩下一筆，大約需要經過幾層。

以 8 筆資料來說，大約經過 3 層。而每一層仍然需要處理資料，因此 Quick Sort 的平均時間複雜度是：

O(n log n)

但如果 Pivot 每次都把資料切得很不平均，情況就不一樣了。

例如資料原本是：

[1, 2, 3, 4, 5, 6, 7, 8]

假設每次都選擇最右邊的數字當 Pivot。

第一次選擇 8：

[1, 2, 3, 4, 5, 6, 7] | 8 | []
        7 筆           Pivot  0 筆

因為其他數字全部都比 8 小，所以 Pivot 左邊有 7 筆，右邊卻完全沒有資料。

接著繼續處理左邊的 7 筆，這次 Pivot 是 7：

[1, 2, 3, 4, 5, 6] | 7 | []
        6 筆        Pivot  0 筆

下一次 Pivot 是 6：

[1, 2, 3, 4, 5] | 6 | []
      5 筆       Pivot  0 筆

整個過程就會變成：

8 筆 → Pivot 8 → 左邊 7 筆、右邊 0 筆
7 筆 → Pivot 7 → 左邊 6 筆、右邊 0 筆
6 筆 → Pivot 6 → 左邊 5 筆、右邊 0 筆
5 筆 → Pivot 5 → 左邊 4 筆、右邊 0 筆
...

這就是切分不平均：每次選完 Pivot，都只有一筆資料被確定下來，剩下的大部分資料還要繼續處理。

所以 Quick Sort 雖然平均時間複雜度是 O(n log n)，但如果每次 Pivot 都造成這種非常不平均的切分，最差時間複雜度就可能來到：

O(n²)

這也是為什麼 Pivot 如何把資料切開，會影響 Quick Sort 的效率。

這裡的 Quick Sort 複雜度整理參考自 Ralph Tech〈快速排序 Quick Sort〉。

Dijkstra：這次看的不只是資料有幾筆

Dijkstra 又不太一樣，因為它解決的不是排序，而是 Graph 的最短路徑問題。

它的核心流程是：

從起點出發 → 找 Neighbor → 更新 Distance → 選出下一個距離最近的 Vertex → 重複處理。

「Dijkstra 演算法的時間複雜度取決於使用的資料結構。」
這句話引用自 iThome－Dijkstra Algorithm。

前面 Bubble Sort、Quick Sort，我主要都是看 Array 有多少筆資料；到了 Dijkstra，除了 Vertex 數量之外，Graph 有多少條 Edge、使用什麼方式記錄 Neighbor，以及怎麼找出下一個距離最小的 Vertex，都可能影響執行效率。

所以即使兩張 Graph 都有 8 個 Vertex，如果 Edge 數量不同，需要檢查的 Neighbor 數量也可能不同。

另外，如果 Vertex、Edge 都相同，只改變 Weight，最後找到的最短路徑可能會改變，但不代表 Weight 數字越大，時間複雜度就越高。

Dijkstra 的時間複雜度不像前面的排序一樣，只看一個 n 就能理解，使用什麼資料結構也是分析效率的一部分。

最後把三種演算法放在一起

一開始學 Big O 時，我只知道 O(n²) 比 O(n log n) 成長得更快，卻沒有什麼實際感覺。

直到真的寫過 Bubble Sort、Quick Sort，再一路做到 Dijkstra，我才開始發現：

Bubble Sort 讓我看到資料越多，比較次數會怎麼增加；Quick Sort 讓我發現同樣是排序，不同的處理方式會有不同的效率；到了 Dijkstra，又進一步發現資料結構也會影響演算法的效率。

所以現在再回頭看 Day 4 的 Big O，好像終於不再只是 O(n)、O(n²) 這些看起來很像數學公式的東西了。

Big O 真正想告訴我的，是當資料越來越多時，我現在選擇的這個方法，成本會怎麼跟著成長。

下一篇進入部屬囉

參考資料

• AppWorks School－初學者學演算法：談什麼是演算法和時間複雜度
• Ralph Tech－演算法學習筆記：氣泡排序
• Ralph Tech－快速排序 Quick Sort
• Medium－Dijkstra's Algorithm
• iThome－Dijkstra Algorithm