如何精準評估演算法效率？掌握計算複雜度，提升程式碼執行速度

演算法效率是什麼？

在軟體開發與資料結構的世界中，撰寫正確無誤的程式固然重要，但更關鍵的是，如何讓程式碼執行得更快、更省資源。因此，學會評估演算法的效率，並據此優化程式碼，是每位程式設計師必須掌握的核心能力。

Table of Contents

一、為何需要評估演算法效率？

隨著資料量激增，演算法效率的影響愈發明顯。不論是搜尋資料、排序數據，還是處理大量用戶請求，高效的演算法能讓程式執行時間大幅縮短，減少系統資源消耗，提升使用者體驗。因此，若忽略演算法效率，即便功能再完整的程式，也可能因效能瓶頸而變得難以實用。

二、時間複雜度與空間複雜度的定義

1. 時間複雜度（Time Complexity）

時間複雜度表示演算法執行時間隨輸入規模變化的關係。常見的時間複雜度表示方式如下，以輸入規模 n 表示：

O(1)：常數時間，不論資料量多大，執行時間固定不變。
O(log n)：對數時間，每次操作資料量減半，例如二分搜尋。
O(n)：線性時間，隨著資料量增長，執行時間等比例增加。
O(n log n)：線性對數時間，例如高效排序演算法（如合併排序、快速排序）。
O(n^2)：平方時間，常見於巢狀迴圈處理，例如冒泡排序。
O(2^n)：指數時間，常見於遞迴解法，如費波那契數列暴力解法。
O(n!)：階乘時間，極端情況，如排列組合的完全搜尋。

這些大 O 表記法（Big O Notation）提供了一種理論上的估算，幫助我們粗略了解演算法在資料量增長時的性能表現。

2. 空間複雜度（Space Complexity）

空間複雜度表示演算法執行過程中所需的額外記憶體空間，主要關注變數、資料結構、遞迴堆疊等佔用的資源。例如：

O(1)：常數空間，只需要固定大小的額外空間。
O(n)：線性空間，需隨輸入資料量成比例擴增，例如使用輔助陣列。

空間與時間複雜度往往需要權衡，某些情況下使用更多空間可換取更快的執行速度。

三、如何評估自己的演算法效率？

1. 理論分析

在撰寫程式前，先用數學方法分析程式的時間與空間複雜度。例如：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 常數時間操作
    }
}

上述程式具有 O(n^2) 的時間複雜度，因為內外兩層迴圈分別執行 n 次。

2. 實測分析

理論分析可估算大致效率，但在實務中，還需考慮：

硬體性能
編譯器優化
特定資料分布（如最佳、最壞、平均情況）

使用工具如：

Python：time 模組、timeit 庫
C++：chrono 庫
Java：System.nanoTime()

這些工具能測量程式實際執行時間，輔助理論分析結果。

四、演算法效能提升技巧與最佳實踐

1. 降低時間複雜度

選擇高效演算法：例如，使用 O(n log n) 的快速排序代替 O(n^2) 的冒泡排序。
減少重複計算：例如，動態規劃避免遞迴中的重複子問題。
利用資料結構優勢：哈希表 O(1) 查詢速度優於陣列 O(n) 的線性搜尋。

2. 減少空間消耗

原地操作：避免額外使用輔助陣列，如原地快速排序。
重複使用變數：避免不必要的暫存變數。

3. 平衡時間與空間

某些情況下，犧牲空間換取時間可提升整體性能。例如，透過建立查找表（Hash Table），可在 O(1) 時間內查找資料，儘管耗費更多記憶體。

4. 注意資料特性

演算法性能與資料分布息息相關。例如：

已排序資料可用二分搜尋，速度快於線性搜尋。
資料稀疏時，可使用稀疏矩陣來節省空間。

五、常見錯誤與性能瓶頸排除方法

案例一：搜尋問題

需求：在一個長度為 n 的已排序陣列中搜尋特定數字。

解法對比：

線性搜尋：O(n)
二分搜尋：O(log n)

若 n 很大，二分搜尋明顯更具優勢。

案例二：排序問題

需求：對長度為 n 的陣列進行排序。