Big O 表示法

11.1 定義 Big O 表示法

Big O 表示法是數學表示法，用來描述算法執行時間或資源消耗的上限，這取決於輸入資料的大小。它能幫助我們了解算法隨著數據量增加時的擴展性和性能變化。

Big O 表示法會專注於算法中最重要的部分，忽略常數和不太重要的項目，以專注於算法的長期行為。

主要表示法：

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

• 算法的運行時間與輸入大小無關。
• 示例：根據索引訪問陣列元素。

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

• 算法運行時間與輸入大小呈線性關係。
• 示例：簡單地遍歷陣列中的所有元素。

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

• 算法運行時間隨著輸入大小以對數方式增長。
• 示例：已排序陣列中的二分搜尋。

O(n^2) — 平方時間複雜度：

• 算法運行時間與輸入大小的平方成正比。
• 示例：冒泡排序，插入排序。

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

• 算法運行時間與輸入大小指數成正比。
• 示例：用全面方式解決背包問題。

注意：你會在後續講座中更詳細地了解二分搜尋、冒泡排序和「背包問題」。

11.2 解釋 Big O 表示法

如何解讀和使用 Big O 表示法？

忽略常數和不太重要的項目： Big O 描述的是函數的增長率，忽略常數和不太重要的項目。例如，O(2n) 和 O(3n) 被解釋為 O(n)。

比較算法： Big O 允許我們根據漸近效率比較算法。例如，具有 O(n log n) 的算法比 O(n^2) 的算法對於非常大量的數據更有效率。

最壞情況分析： Big O 通常用於分析算法在最壞情況下的執行時間，以評估其最大複雜度。

忽略常數

看看忽略常數和不太重要的項目的例子：

示例 1. 考慮兩個函數：

• f(n) = 3n + 2
• g(n) = 5n + 1

這兩個函數都有線性複雜度，因為每個函數的主導項是 n。因此，儘管系數和附加項不同，這兩個函數都被解釋為 O(n)。

示例 2. 考慮兩個函數：

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

這兩個函數都有平方複雜度，因為主導項是 n^2。不考慮其他項和系數，這兩個表達式都被解釋為 O(n^2)。

11.3. 比較算法

1. 在非常大量數據下比較算法

示例 1：

• 算法 A 的時間複雜度是 O(n^2)。
• 算法 B 的時間複雜度是 O(n log n)。

對於小值的 n，算法 A 可能由於較小的常數而運行得更快，但對於大值的 n，算法 B 會更快，因為其增長是對數而非平方。

示例 2：

• 算法 X 的時間複雜度是 O(n)。
• 算法 Y 的時間複雜度是 O(1)。

無論 n 的大小如何，算法 Y 都會更快，因為 O(1) 表示算法的運行時間與輸入數據大小無關。

2. 最壞情況分析

示例 1：

冒泡排序在最壞情況下的時間複雜度為 O(n^2)，當數組按反序排列時。這意味著對於每個元素在數組中，可能需要與每個其他元素進行比較和交換。

示例 2：

二分查找在最壞情況下的時間複雜度為 O(log n)。這意味著即使在最壞情況下，找到元素所需的步驟數也將與數組大小呈對數關係，非常高效。

3. 對性能和可擴展性的影響

示例 1：

假設我們有兩個處理數據的算法，一個的時間複雜度為 O(n^2)，另一個為 O(n log n)，如果我們將數據大小從 1000 個元素增加到 10 000 個元素，性能的差異將非常顯著。

• O(n^2) 的算法將對 10 000 個元素執行大約 100 000 000 次操作。
• O(n log n) 的算法將對 10 000 個元素執行約 40 000 次操作。

示例 2：

考慮一個時間複雜度為 O(2^n) 的算法。如果我們將輸入數據從 10 個增加到 20 個元素，操作數將呈指數增加。

• 對於 n = 10: 2^10 = 1024 次操作。
• 對於 n = 20: 2^20 = 1 048 576 次操作。

這表明指數複雜度對於大數值的 n 是如何迅速變得不切實際。