演算法的時間複雜度和空間複雜度是評估演算法效能的兩個重要指標，這些指標幫助我們理解演算法在不同情況下的效率和資源需求。

時間複雜度 (Time Complexity)

時間複雜度表示演算法執行所需的時間隨輸入數據的大小（通常記作 n）變化的程度。它通常以大O符號來表示，描述的是最壞情況下的運行時間增長趨勢。

常見的時間複雜度有：

• O(1): 常數時間，表示演算法的執行時間不隨輸入大小變化。
• O(log n): 對數時間，典型的例子是二分搜尋。
• O(n): 線性時間，表示演算法的執行時間與輸入大小成正比。
• O(n log n): 線性對數時間，常見於高效的排序演算法如歸併排序或快速排序。
• O(n^2): 平方時間，表示執行時間與輸入大小的平方成正比，典型例子是簡單的排序演算法如冒泡排序。
• O(2^n): 指數時間，通常在解決複雜問題如遞迴算法時出現。
• O(n!): 階乘時間，出現在解決排列組合問題的暴力方法中。

空間複雜度 (Space Complexity)

空間複雜度表示演算法在執行過程中所需的額外記憶體空間，這也通常以大O符號表示。它包括了用於存儲輸入數據的空間以及演算法在執行時需要的額外空間。

常見的空間複雜度有：

• O(1): 常數空間，表示演算法所需的額外空間不隨輸入大小變化。
• O(n): 線性空間，表示所需的額外空間與輸入數據的大小成正比。
• O(n^2): 平方空間，常見於使用二維矩陣的演算法，如某些圖論算法。

時間複雜度與空間複雜度的平衡

通常在設計演算法時，時間複雜度和空間複雜度之間存在一個平衡。在某些情況下，為了提高速度，可以使用更多的記憶體（例如，使用額外的數據結構來加快查找速度），反之亦然。

理解這兩個指標有助於選擇和設計更有效的演算法，特別是在處理大規模數據或在資源有限的環境下工作時。

例子1: 線性搜尋 (Linear Search)

線性搜尋是一個非常簡單的演算法，用來在一個列表中查找特定元素。

問題: 給定一個長度為 n 的列表，我們要查找一個特定的元素。

演算法:

1. 從列表的第一個元素開始，逐一檢查每個元素是否等於目標元素。
2. 如果找到目標元素，返回其位置；如果到達列表末尾仍未找到，返回不存在。

時間複雜度:

• 在最壞的情況下（即目標元素在列表的最後或不存在），需要檢查所有的 n 個元素，因此時間複雜度為 O(n)。

空間複雜度:

• 除了輸入的列表外，演算法只需要常數空間來存儲索引和目標元素，因此空間複雜度為 O(1)。

例子2: 二分搜尋 (Binary Search)

二分搜尋是一種效率更高的搜尋方法，但前提是列表必須是已排序的。

問題: 給定一個已排序的長度為 n 的列表，我們要查找一個特定的元素。

演算法:

1. 設定兩個指標，分別指向列表的起點和終點。
2. 計算中間位置的索引。
3. 如果中間位置的元素等於目標元素，返回其位置；如果目標元素小於中間元素，將終點指標移動到中間位置的左邊；如果目標元素大於中間元素，將起點指標移動到中間位置的右邊。
4. 重複上述步驟，直到找到目標元素或搜索範圍縮小為空。

時間複雜度:

• 每次搜索範圍都會減半，這意味著最多需要進行 log n 次比較，時間複雜度為 O(log n)。

空間複雜度:

• 如果使用迭代方式（而非遞迴），演算法只需要常數空間來存儲指標，因此空間複雜度為 O(1)。

例子3: 冒泡排序 (Bubble Sort)

冒泡排序是一種簡單但低效的排序演算法。

問題: 給定一個長度為 n 的未排序列表，我們要對其進行排序。

演算法:

1. 重複地遍歷列表，相鄰的元素進行比較，並將較大的元素向後移動。
2. 每次遍歷後，最大的元素會被移動到正確的位置。
3. 重複這個過程直到列表完全有序。

時間複雜度:

• 在最壞情況下，列表是反序的，需要進行 n-1 次遍歷，每次遍歷最多進行 n-1 次比較，因此時間複雜度為 O(n^2)。

空間複雜度:

• 冒泡排序是一種原地排序演算法，不需要額外的數據結構來存儲數據，因此空間複雜度為 O(1)。

例子4: 快速排序 (Quicksort)

快速排序是一種高效的排序演算法，通常在實踐中表現良好。

問題: 給定一個長度為 n 的未排序列表，我們要對其進行排序。

演算法:

1. 從列表中選擇一個基準點（pivot）。
2. 將列表分成兩部分：小於基準點的元素和大於基準點的元素。
3. 對這兩部分分別進行快速排序。
4. 將排好序的部分合併起來。

時間複雜度:

• 在最壞情況下（例如基準點選得很糟糕），時間複雜度為 O(n^2)；但在平均情況下，時間複雜度為 O(n log n)。

空間複雜度:

• 快速排序的原地排序版本需要 O(log n) 的空間來存儲遞迴調用的堆棧。

結論

這些例子展示了不同演算法的時間複雜度和空間複雜度如何隨著問題的性質和演算法的設計而變化。在選擇或設計演算法時，我們通常希望在合理的時間內完成任務，並且不使用過多的資源。因此，理解這些複雜度的概念有助於我們在實際應用中做出更好的決策。