時間複雜度和空間複雜度的分析，例如：某演算法的 Big-O 表示法。

 好的，時間複雜度和空間複雜度是衡量演算法效率的兩個最重要的指標。它們通常使用 大 O 符號 (Big O Notation) 來表示。

---

什麼是演算法複雜度？

• 時間複雜度 (Time Complexity): 衡量演算法執行所需時間的成長趨勢。它並不是指演算法實際執行了多少秒，而是指隨著輸入數據規模的增加，演算法執行步數或基本操作次數的成長速度。
• 空間複雜度 (Space Complexity): 衡量演算法執行所需記憶體空間的成長趨勢。它指的是隨著輸入數據規模的增加，演算法在運行時需要額外佔用的記憶體空間大小。

---

為什麼要分析複雜度？

• 評估效率： 幫助我們評估不同演算法在處理大量數據時的性能。
• 選擇演算法： 在多個解決方案中，選擇最適合特定場景的演算法。
• 預測性能： 估計演算法在更大數據集上的表現。
• 優化： 找出演算法的瓶頸，為優化提供方向。

---

大 O 符號 (Big O Notation)

大 O 符號是一種數學表示法，用於描述函式或演算法在輸入數據量趨於無窮大時的漸近上限。它只關心成長的趨勢，會忽略常數因子和低階項，因為它們在輸入規模非常大時的影響微乎其微。

例如，如果一個演算法的執行時間是 $f(n)=3n^2+2n+5$，當 n 變得非常大時，n2 項的增長速度會遠快於 2n 和 5。所以，我們會說這個演算法的時間複雜度是 O(n2)。

常見的大 O 符號類別 (由快到慢，效率由高到低)

1. $O(1)$ (常數時間 / Constant Time):

   • 定義： 無論輸入數據的規模多大，演算法的執行時間或所需空間都是固定的。
   • 範例：
     • 陣列根據索引存取元素 (arr[5])。
     • 將一個變數賦值給另一個變數。
     • 哈希表中插入或尋找元素 (平均情況)。
   • 場景： 任何基本算術運算。

2. $O(\log N)$ (對數時間 / Logarithmic Time):

   • 定義： 執行時間或所需空間隨著輸入規模的增加而對數增加。通常發生在每次迭代都將問題規模減半的演算法中。
   • 範例：
     • 二分搜尋 (Binary Search)。
     • 在平衡二元搜尋樹中插入或尋找元素。
   • 場景： 在大型排序數據集中尋找特定元素。

3. $O(N)$ (線性時間 / Linear Time):

   • 定義： 執行時間或所需空間與輸入數據的規模成正比。
   • 範例：
     • 遍歷一個陣列或鏈結串列。
     • 尋找陣列中的最大或最小元素。
     • 對單個迴圈執行 N 次操作。
   • 場景： 需要遍歷整個數據集的演算法。

4. $O(N\log N)$ (線性對數時間 / Linearithmic Time):

   • 定義： 執行時間或所需空間以 N 乘以 logN 的速度增長。通常發生在「分而治之」的排序演算法中。
   • 範例：
     • 合併排序 (Merge Sort)。
     • 快速排序 (Quick Sort) 的平均情況。
     • 堆積排序 (Heap Sort)。
   • 場景： 許多高效的排序演算法都屬於此類。

5. $O(N^2)$ (平方時間 / Quadratic Time):

   • 定義： 執行時間或所需空間與輸入規模的平方成正比。通常發生在嵌套迴圈，每個迴圈都遍歷整個數據集的情況。
   • 範例：
     • 冒泡排序 (Bubble Sort)。
     • 選擇排序 (Selection Sort)。
     • 插入排序 (Insertion Sort)。
     • 遍歷二維陣列 (N x N)。
   • 場景： 當你需要比較或處理數據集中所有可能的配對時。

6. $O(2^N)$ (指數時間 / Exponential Time):

   • 定義： 執行時間或所需空間與輸入規模的指數倍成正比。這類演算法的效率非常低，只能處理很小的輸入。
   • 範例：
     • 斐波那契數列的遞迴實現 (未最佳化)。
     • 旅行推銷員問題 (Brute-force)。
     • 子集生成。
   • 場景： 通常出現在暴力搜尋或嘗試所有可能組合的問題中。

7. $O(N!)$ (階乘時間 / Factorial Time):

   • 定義： 執行時間或所需空間與輸入規模的階乘成正比。這是最糟糕的複雜度之一，通常只適用於極小規模的輸入。
   • 範例：
     • 生成所有排列 (Permutations)。
     • 某些旅行推銷員問題的暴力解法。
   • 場景： 極端複雜的組合問題。

---

如何分析複雜度？

時間複雜度分析步驟：

1. 找出基本操作： 確定演算法中最耗時的操作（例如：比較、賦值、算術運算、陣列存取）。
2. 計算操作次數： 估計基本操作的執行次數與輸入規模 N 的關係。
3. 忽略常數和低階項： 根據大 O 符號的定義，只保留最高階項並忽略常數係數。

範例：

PHP

function sumArray(array $arr): int {
    $sum = 0; // O(1)
    for ($i = 0; $i < count($arr); $i++) { // 迴圈執行 N 次 (如果 arr 長度為 N)
        $sum += $arr[$i]; // 每次迴圈 O(1) 操作
    }
    return $sum; // O(1)
}

• 基本操作：$sum += $arr[$i]
• 迴圈執行 N 次。
• 總操作數約為 $1+N\times 1+1=N+2$。
• 忽略常數和低階項，時間複雜度為 O(N)。

PHP

function findPairs(array $arr): void {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) { // 外層迴圈 N 次
        for ($j = 0; $j < $n; $j++) { // 內層迴圈 N 次
            echo $arr[$i] . " " . $arr[$j] . "\n"; // O(1)
        }
    }
}

• 基本操作：echo $arr[$i] . " " . $arr[$j] . "\n";
• 外層迴圈執行 N 次，內層迴圈執行 N 次。
• 總操作數約為 $N\times N=N^2$。
• 時間複雜度為 O(N2)。

空間複雜度分析步驟：

1. 找出額外空間： 確定演算法執行過程中額外佔用的記憶體空間（不包括輸入數據本身）。
2. 計算空間大小： 估計額外空間與輸入規模 N 的關係。
3. 忽略常數： 同樣只保留最高階項並忽略常數係數。

範例：

PHP

function createDoubledArray(array $arr): array {
    $doubled = []; // O(1) 初始
    foreach ($arr as $item) { // 迴圈 N 次
        $doubled[] = $item * 2; // 每次迴圈，新增一個元素到 $doubled 陣列
    }
    return $doubled;
}

• 額外空間：$doubled 陣列。
• 當迴圈結束時，$doubled 陣列將包含 N 個元素 (與輸入陣列 arr 的長度相同)。
• 空間複雜度為 O(N)。

PHP

function sumArrayInPlace(array $arr): int {
    $sum = 0; // O(1)
    // 這裡我們假設 arr 是輸入，但不計入額外空間
    for ($i = 0; $i < count($arr); $i++) {
        $sum += $arr[$i];
    }
    return $sum;
}

• 額外空間：只有一個變數 $sum，其大小不隨輸入陣列的長度改變。
• 空間複雜度為 O(1)。

---

掌握時間複雜度和空間複雜度的分析是成為一個優秀程式設計師的關鍵，它能幫助你寫出更有效率、更具擴展性的程式碼。