時間複雜度的理解以及常見的演算法

New Zealand - Deer Park Heights Queenstown

前言

除了時間複雜度，也會順便簡單說明相關東西，如下：

相關演算法：

• 二元搜尋（Binary search）
• 快速排序（Quick sort）
• 合併排序（Merge sort）
• 氣泡排序（Bubble sort）
• 插入排序（Insertion sort）
• 動態規劃（Dynamic Programming）
• 貪婪演算法（Greedy Algorithm）

經典問題：

• 子集問題（Subset problem）
• 背包問題（Knapsack problem）
• 旅行推銷員問題（Travelling Salesman Problem, TSP）

其他相關知識：

• 費氏數列（Fibonacci Sequence）

時間複雜度

O(n) — 線性時間複雜度

演算法的執行時間隨輸入資料規模成正比。例如，for-loop 一個長度為 n 的陣列，每個值都訪問一次，這就是 O(n)。

O(1) — 常數時間複雜度

這種複雜度表示演算法的執行時間不會隨輸入資料規模改變。例如，從陣列中取得某個值

let array = [5, 2, 10]

array[1] // 2

array[index] 的操作是 O(1)。 還有像是 hash table 的讀取，平均起來也是 O(1)，只不過在最壞的情況，設計不良，導致大量碰撞，那麼所有的值可能被存放在同一個桶（bucket）中，哈希表的時間複雜度就會退化到 O(n)，這與線性結構（如鏈表）相似。

Hash Table（哈希表)

簡單說明什麼 Hash Table（哈希表)，它是一種用來快速查找數據的資料結構。它能夠在幾乎時間（O(1)）內完成插入、刪除和查找操作，這讓它非常高效，特別是在需要頻繁存取的情況下。 如何運作？

• 鍵（Key）和值（Value）：Hash Table 使用一個「鍵」來對應到一個「值」。比如說，你可以用「名字」作為鍵，然後將「電話號碼」作為值存入 Hash Table 裡。
• 哈希函數（Hash Function）：為了快速找到某個鍵對應的值，Hash Table 使用一個哈希函數來將鍵轉換成一個「哈希值」。這個哈希值是一個數字，用來決定這個鍵應該存放在哪裡。
• 儲存結構：Hash Table 本質上是一個陣列，哈希函數會將鍵轉換成一個索引值，然後將值儲存在這個位置。

所以可以想像，假設今天想在電話簿搜尋某個人的電話，一個一個查找一定是最慢的，假設我們直接輸入一些名字關鍵字，例如要找的人叫做 Tim，我們搜尋 T，就會馬上篩選出 T 開頭的人，這樣查找下來一定是比一個一個找還快。

O(log n) — 對數時間複雜度

這種複雜度表示每次迭代或操作都能將問題規模縮小一半，常見於二分搜尋演算法。例如，搜尋一個已排序的陣列中的某個值就是 O(log n)。

• 二分搜尋法

假設你有一個已經按大小排序的陣列，比如說 [2, 4, 6, 8, 10, 12, 14]，你想要找出 10 的位置。二分搜尋的步驟如下：

1. 設定起點和終點：一開始，設定兩個指標：左邊界 指向數列的起始位置，右邊界 指向數列的結尾位置。
2. 找中點：計算中點的位置 mid = (左邊界 + 右邊界) / 2，然後檢查中點的值。
3. 比較中點的值：

• 如果中點的值等於你要找的目標值，搜尋成功，返回中點的位置。
• 如果中點的值比目標值小，目標值一定在中點的右邊。因此，你將 左邊界 移到 mid + 1。
• 如果中點的值比目標值大，目標值一定在中點的左邊。因此，你將 右邊界 移到 mid - 1。

4. 重複步驟 2 和 3，直到找到目標值或搜尋範圍變空（即 左邊界 超過 右邊界），代表目標值不在數列中。

轉換成程式碼的話

func binarySearch(array: [Int], target: Int) -> Int? {

    var left = 0

    var right = array.count - 1

    while left <= right {

        let mid = (left + right) / 2

        let midValue = array[mid]

        if midValue == target {

            return mid // 找到目標值，返回索引

        } else if midValue < target {

            left = mid + 1 // 目標在右邊，縮小搜尋範圍

        } else {

            right = mid - 1 // 目標在左邊，縮小搜尋範圍

        }    }    return nil // 找不到目標值

}// 使用範例

let numbers = [2, 4, 6, 8, 10, 12, 14]

if let index = binarySearch(array: numbers, target: 10) {

    print("找到了！數字 10 在索引 \(index) 上。")

} else {

    print("找不到目標數字。")

}

O(n log n) — 線性對數時間複雜度

常見於高效排序演算法，如快速排序（Quick Sort）和合併排序（Merge Sort）。這種複雜度表示執行的操作數量大約是 n 個值進行 log n 次處理。這兩個排序法都分而治之（Divide and Conquer） 的策略來解決排序問題。

• 快速排序(Quick Sort)：

原理

快速排序通過選擇一個「基準點（pivot）」來將陣列劃分成兩個部分：

• 所有小於基準點的值移到基準點的左邊
• 所有大於基準點的值移到基準點的右邊

這樣將陣列分割成較小的部分後，對左右部分遞迴地進行快速排序，直到每個部分只有一個或零個值，排序完成。

步驟

1. 從陣列中選擇一個基準點（通常可以選擇第一個、最後一個或中間的值，或者隨機選擇）。
2. 將陣列分成兩部分：一部分的所有值都小於基準點，另一部分的所有值都大於基準點。
3. 對兩個部分分別遞迴地應用快速排序。
4. 合併結果，最終得到排序好的陣列。

時間複雜度

• 最壞情況: O(n²)，當基準點選擇不佳（例如，已排序或逆序陣列中每次選擇的基準點都是最大或最小值）。
• 平均情況: O(n log n)，當基準點將陣列合理地劃分成大致相等的兩部分時。
• 最好情況: O(n log n)，當每次分割都能將陣列對半分時。

優點

• 快速排序在一般情況下比其他 O(n log n) 排序演算法更快，因為其內部處理過程優化了內存使用，並且常數因子較小。
• 原地排序（in-place），不需要額外的空間來存儲數據。

缺點

• 不穩定排序演算法（不保留相同值之間的相對順序）。
• 對於基準點選擇不佳的情況，效率會顯著降低。

• 合併排序(Merge Sort)：

原理

合併排序將陣列分成兩個部分，遞迴地將每個部分繼續分割，直到每個部分只有一個值。然後將這些部分進行合併，將兩個已排序的小陣列合併成一個較大的已排序陣列，直到合併完成。

步驟

1. 將陣列對半分割，直到每個子陣列只有一個值。
2. 將兩個已排序的子陣列合併成一個排序好的陣列，直到合併成最終排序好的陣列。
3. 遞迴重複以上步驟。

時間複雜度

• 最壞情況: O(n log n)
• 平均情況: O(n log n)
• 最好情況: O(n log n)

優點

• 穩定排序演算法（相同值的順序保持不變）。
• 對於大型陣列具有穩定的性能，無論初始數據排列方式如何，時間複雜度始終是 O(n log n)。

缺點

• 需要額外的空間來存儲臨時數據，空間複雜度為 O(n)。
• 相較於原地排序演算法，對內存使用較多，尤其在處理大型數據集時。

比較兩個排序法

空間複雜度:

• 快速排序: O(1)（原地排序，不需要額外空間）
• 合併排序: O(n)（需要額外空間來合併子陣列）

穩定性:

• 快速排序: 不穩定
• 合併排序: 穩定

性能:

• 快速排序通常比合併排序更快，但在最壞情況下可能表現不佳。
• 合併排序性能穩定，適合大型數據集。

O(n²) — 平方時間複雜度

這種複雜度通常來自巢狀迴圈（nested loops）。例如，對一個 n 值的陣列執行兩層巢狀迴圈，每個值都與其他值配對，這就是 O(n²)。像是氣泡排序（Bubble Sort）和插入排序（Insertion Sort）這類排序演算法。

• 氣泡排序（Bubble Sort)

原理

氣泡排序透過不斷比較和交換相鄰的值，將較大的值「冒泡」到陣列的末端。這個過程會多次重複，直到整個陣列排序完成。

步驟

1. 從陣列的第一個值開始，與相鄰的值比較大小。
2. 如果前一個值大於後一個值，交換它們的位置。
3. 繼續向後比較並交換，直到陣列的末尾。這樣最大或最小的值會被移動到末尾位置。
4. 重複這個過程 n-1 次（n 是陣列長度），直到沒有需要交換的值為止。

時間複雜度

• 最壞情況: O(n²)，當陣列為逆序排列時，需進行大量交換操作。
• 平均情況: O(n²)
• 最好情況: O(n)，當陣列已排序時，只需一輪比較即可。

優點

• 實現簡單，適合教學和小型資料集。
• 若陣列已大部分排序，則可以進行優化（例如，設置一個標誌變數來檢測是否發生交換，若沒有交換則排序完成）。

缺點

• 效率低，當資料規模增大時表現不佳，時間複雜度較高。
• 無法有效應對大數據集，因為它的交換次數較多。

• 插入排序（Insertion Sort)

原理

插入排序通過逐個處理每個值，將其插入到前面已排序部分的適當位置。每次處理一個新的值時，會從後往前逐一比較，將該值插入到正確位置。

步驟

1. 將第一個值視為已排序部分，從第二個值開始處理每個值。
2. 將當前值與前面已排序部分的值逐一比較，找到適合插入的位置，並將較大的值向後移動。
3. 重複這個過程，直到所有值都被插入到正確的位置。

時間複雜度

• 最壞情況: O(n²)，當陣列為逆序排列時，需進行大量移動操作。
• 平均情況: O(n²)
• 最好情況: O(n)，當陣列已排序或接近排序時，插入排序會非常高效。

優點

• 實現簡單，適合小型資料集或部分排序的資料集。
• 穩定排序演算法，保持相同值的相對順序不變。
• 當資料幾乎排序時，插入排序表現非常好，效率高。

缺點

• 效率低，尤其在大規模資料集上，時間複雜度較高。
• 對於未排序或亂序程度高的陣列，表現不如其他高效演算法（如快速排序或合併排序）。

比較兩個排序法

簡單性:

• 氣泡排序和插入排序都非常容易理解和實現，適合教學使用。

效率:

• 氣泡排序的效率較低，因為交換操作多，較少應用於實際問題。
• 插入排序在小型資料集或部分排序的資料上表現良好，效率較高。

穩定性:

• 氣泡排序和插入排序都是穩定的排序演算法。

什麼時候使用？

• 氣泡排序 幾乎不會在實際應用中使用，只適合教學目的。
• 插入排序 適合小型資料集，或用於已部分排序的資料集進行微調。

O(2^n) — 指數時間複雜度

這種複雜度非常高，代表問題的規模每增加一個單位，執行時間會指數增長。例如，解決所有可能的子集問題（Subset Problem）、背包問題（Knapsack Problem）、費氏數列（Fibonacci Sequence）或某些遞迴演算法，在實際應用中，通常需要使用更高效的演算法，例如，動態規劃（Dynamic Programming）或貪婪演算法（Greedy Algorithm）來替代指數時間複雜度的解法，以便處理更大規模的問題。

• 子集問題（Subset Problem）

假設你有一個包含 n 個值的集合，並且你想找到這個集合的所有子集。每個值都有兩種狀態：包含在子集中或不包含在子集中。這樣就有 2^n 個可能的子集。當集合的大小增長時，計算所有子集的時間將以 2^n 的速度增長。

舉例來說，假設有集合 {A, B, C}，我們希望找出這個集合的所有子集。

• 空集合 {} → 1 種
• 單值子集 {A}, {B}, {C} → 3 種
• 雙值子集 {A, B}, {A, C}, {B, C} → 3 種
• 全集合 {A, B, C} → 1 種

這樣等於 1 + 3 + 3 + 1 = 8 ，也就是有 2³ = 8，共有8種。

• 背包問題（Knapsack Problem）

背包問題是一個經典的優化問題，問題是這樣的：

假設你有一個背包，這個背包有一個最大容量（如重量限制）。

你有 n 個物品，每個物品都有自己的重量和價值。

目標是選擇一些物品放入背包，使得在不超過背包容量的情況下，選中的物品總價值最大。

假設你有一個背包，最大承重為 4 公斤，你有以下物品可以選擇：

1. 餅乾：重量 1 公斤，價值 3
2. 蘋果：重量 3 公斤，價值 4
3. 水：重量 4 公斤，價值 6

你需要找到一個選擇方案，使得放入背包的物品總價值最大且不超過 4 公斤。例如，選擇餅乾和 蘋果可以獲得總價值 3 + 4 = 7，而總重量剛好是 1 + 3 = 4 公斤。

我們先用圖表來呈現，會比較好理解，用二維分別代表物品和重量，程式裡我們常會用 dp[i][j] ，i 通常代表物品而 j 代表重量，當然想用其他的詞代替也可以。

我們先把最簡單的填完，假設背包只有0公斤的時候，所有物品都不能裝，所以0公斤那行全部為價值0。

再來想像現在就只有餅乾這個物品，所以餅乾那列全部只能得到價值3，就算背包有2公斤以上都一樣，因為現在能選的物品只有餅乾。

再來就有趣了，因為現在出現了新的物品可以選擇，所以我們就一格一格講解

• [1, 1] 這格，背包有1公斤，所以只能選擇餅乾，所以是價值3
• [1, 2] 這格，背包有2公斤，目前也只能選擇餅乾裝，蘋果3公斤還無法選擇
• [1, 3] 這格，背包有3公斤，我們可以選擇蘋果了，很明顯3公斤時，選擇蘋果是最佳解，他有價值4，大於餅乾的價值3，所以這格填4。
• [1, 4] 這格，背包有4公斤，我們很容易知道，這時剛好可以放兩個東西，把餅乾跟蘋果都裝進來，剛好是4公斤，所以價值是 3 + 4 = 7，用程式表示就是 dp[1][4] 。

最後是加入了水這個物品，它有4公斤價值6，但我相信這列一定很好填，背包4公斤前都和上面那列一樣，因為水太重了，不能裝，而只有到4公斤的時候要考慮是否要裝水還是選上列 (dp[1][4]) ，但很明顯只選水只有6的價值，所以要選 dp[1][4] 價值7才是最佳解。

所以當背包有4公斤時最佳選擇就是選餅乾和蘋果，價值最大化7，用程式表示就是 dp[1][4] 。

因為這邊物品很少，所以要推理出來很快，假如遇到物品很多的時候可能就很難那麼直覺知道答案，所以可以用推理的方式，要取得 dp[1][4] ，有兩個情況：

1. 不放蘋果
2. 放蘋果

如果選 1 不放蘋果，表示背包價值是 dp[0][4] 價值3，因為只能放餅乾了。

如果選 2 放蘋果，表示要把背包的重量扣掉蘋果的重量，那就是 4kg — 3kg = 1kg，表示還有一公斤的重量可以放東西，那麼我們前面就推算出來剩一公斤時且只能選餅乾的 dp[0][1] 的最大價值是3，所以最後就變成放入蘋果的情況： dp[0][1] + 蘋果的價值。

因為我們要取得最大值，最後會變成這樣：

dp[1][4] = max(dp[0][4], dp[0][1] + 蘋果的價值)

以上過程在抽象化會變成：

• 不放物品 i：背包容量為 j，裡面不放物品 i 的最大價值是 dp[i - 1][j]。
• 放物品 i：背包空出物品 i 的空間後，背包重量為 j - weight[i] 。 dp[i - 1][j - weight[i]] 為背包重量為 j - weight[i] 且不放物品 i 的最大價值，那麼 dp[i - 1][j - weight[i]] + value[i] （物品 i 的價值），就是背包放物品 i 得到的最大價值。

最後就會得到 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

這問題的優化方法就是使用 動態規劃（Dynamic Programming） 可以將問題的時間複雜度降到 O(n * W)，其中 W 是背包的容量。這個方法更高效，適用於大多數實際情況，後續會再說明清楚如何用動態規劃解決這類型問題。

• 費氏數列（Fibonacci Sequence）

費氏數列是一個著名的數學序列，定義如下：

• 第一個數字是 0，第二個數字是 1。
• 從第三個數字開始，每個數字都是前兩個數字的和。

數列的表達式可以用遞迴公式表示為：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)，當 n ≥ 2。

這樣，我們得到費氏數列的前幾個數字：

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

最簡單但效率不高的方法是用遞迴實作費氏數列。

遞迴解法直接依照定義來計算：

func fibonacci(_ n: Int) -> Int {

    if n <= 1 {

        return n

    }    return fibonacci(n - 1) + fibonacci(n - 2)

}

• 例如，計算 fibonacci(5) 時，函數會展開成：

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(2) = fibonacci(1) + fibonacci(0)

因為每次都會重複計算，導致非常多的冗餘運算，像 fibonacci(3) 會被計算多次。這種遞迴方法的時間複雜度是 O(2^n)，因為每次呼叫都會分裂成兩個新的遞迴呼叫。隨著 n 增加，遞迴樹的節點數量以指數速度增長，導致計算非常低效。

• 動態規劃（Dynamic Programming）

動態規劃是一種將問題拆解成重複子問題，並通過儲存每個子問題的解來避免重複計算的技術。這種方法非常適合解決具有 重疊子問題（Overlapping Subproblems） 和 最優子結構（Optimal Substructure） 性質的問題。

• 重疊子問題：指的是一個大問題可以被分解成許多重複的小問題。例如，剛剛上述說的費氏數列的遞迴計算中，就是有大量重複的子問題，假如每次把算過的資料存起來，就不用一直重複做一樣的事情。
• 最優子結構：指的是一個問題的最優解可以由其子問題的最優解構成。例如，最短路徑問題的解可以由多個更小的最短路徑構成。

解決思路

動態規劃通常使用一個表格來儲存子問題的解。可以有兩種方式來實作動態規劃：

1. 自頂向下（Top-Down Approach，記憶化）：使用遞迴來分解問題，但在每次計算子問題時，會先檢查是否已經計算過並儲存在表格中。如果有，直接返回儲存的結果，否則計算並儲存。
2. 自底向上（Bottom-Up Approach）：從最小的子問題開始解決，逐步計算出更大的問題，並將結果儲存在表格中。

常見例子

1. 費氏數列：用動態規劃可以將時間複雜度從 O(2^n) 降到 O(n)。
2. 最長公共子序列問題（Longest Common Subsequence, LCS）：找出兩個序列的最長公共子序列。
3. 背包問題（Knapsack Problem）：求在容量限制下能夠獲得的最大價值。

用費氏數列來舉例，態規劃方法可以儲存之前計算過的結果，避免重複計算，從而顯著提高效率。

func fibonacci(_ n: Int) -> Int {

    if n <= 1 {

        return n

    }        var fib = [0, 1]

    for i in 2...n {

        fib.append(fib[i - 1] + fib[i - 2])

    }    return fib[n]

}

• 貪婪演算法（Greedy Algorithm）

概念介紹

貪婪演算法是一種在每一步選擇中都作出當前看起來最好的選擇，希望這樣能夠導致全局最優解。貪婪演算法不會回溯或考慮所有可能的情況，它依賴於當前的選擇，因此通常更高效但不一定總能得到最優解。

關鍵點：貪婪演算法的應用場景通常要求問題具有 貪婪選擇性質（Greedy Choice Property），也就是說，局部最優選擇能導致全局最優解。

• 最優子結構：問題的最優解可以分解成子問題的最優解。

解決思路

1. 從問題的初始狀態開始，依次選擇當前的最佳選擇。
2. 一旦做出選擇，就不可改變（即不回溯）。

常見例子

1. 找零問題：使用最少數量的硬幣找零，例如用 1 元、5 元、10 元硬幣找出某個金額。
2. 最小生成樹問題（Minimum Spanning Tree, MST）：Kruskal 演算法和 Prim 演算法都是貪婪演算法。
3. 活動選擇問題（Activity Selection Problem）：選擇最多數量的不相互重疊的活動。

O(n!) — 階乘時間複雜度

階乘複雜度意味著所有排列組合都必須被計算和處理，常見於暴力解法解決排列問題。例如，求解一個 n 個城市的旅行推銷員問題。

階乘時間複雜度是指演算法的執行時間隨輸入大小 n 的階乘（n!）數量級增長。數學上，階乘 n! 定義為：

n!=n×(n−1)×(n−2)×⋯×2×1

對於較小的 n，n! 的增長速度非常快。例如：

• 3!=3×2×1=63!=3×2×1=6
• 5!=5×4×3×2×1=1205!=5×4×3×2×1=120
• 10!=3,628,80010!=3,628,800

旅行推銷員問題（Travelling Salesman Problem, TSP）

是這樣一個問題：假設你是一個推銷員，必須去不同的城市做生意。你的任務是設計一條路線，從某個城市出發，拜訪所有的城市一次，最後回到出發城市，而且希望總行程最短。

關鍵點

• 你有很多城市要走，但每個城市只能去一次。
• 你想找到最短的路線，節省旅途時間和成本。
• 這個問題變得很難，因為當城市數量增加，可能的路線數量會爆炸式增長。

解法

• 暴力解法（Brute Force Approach）：枚舉所有可能的城市訪問順序，計算每條路徑的總距離，然後選擇距離最短的路徑。這種方法需要考慮所有 n! 種排列，時間複雜度為 O(n!)。由於 O(n!) 的增長速度極快，當 n 稍微大一些時，暴力解法在現實中是不可行的。
• 動態規劃 — Held-Karp 演算法
• 分支界限法（Branch and Bound）

一個小結

• 低複雜度（如 O(1)、O(log n) 和 O(n)）通常代表演算法較為高效，適合大規模資料。
• 高複雜度（如 O(n²)、O(2^n) 和 O(n!)）則代表演算法隨著輸入規模增加，性能會急劇下降。