Big O 表示法：基本概念

2.1 定義 Big O 表示法。

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

Big O 表示法專注於算法中最重要的方面，忽略常數和次要項， 這樣可以集中於算法的長期行為。

主要表示法：

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

• 算法的執行時間不取決於輸入數據的大小。
• 例子：通過索引訪問數組中的元素。

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

• 算法的執行時間線性取決於輸入數據的大小。
• 例子：簡單遍歷數組中的所有元素。

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

• 算法的執行時間隨著輸入數據大小的增加而對數增長。
• 例子：在排序數組中的二分搜尋。

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

• 算法的執行時間平方取決於輸入數據的大小。
• 例子：冒泡排序，插入排序。

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

• 算法的執行時間指數取決於輸入數據的大小。
• 例子：使用完全枚舉解決背包問題。

2.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)。

2.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) 的算法將大約執行 100,000,000 次操作，處理 10,000 個元素。
• 具有 O(n log n) 的算法將執行大約 40,000 次操作，處理 10,000 個元素。

例子 2：

考慮一個算法，其運行時間為 O(2^n)。如果我們將輸入數據的大小從 10 增加到 20 元素，則操作次數將指數增長。

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

這說明了為何對於大的 n 值，指數複雜度迅速變得不實用。