大 O 符號是一種數學符號，用于計算機科學中描述算法的效率，特別是時間復雜度和空間復雜度。

它提供了一個上限，描述了隨著輸入數據大小增加，算法的運行時間或內存使用量的增長速度。

大 O 符號主要用于表達以下內容：

• 時間復雜度：衡量算法的運行時間如何隨著輸入大小的變化而變化。例如，時間復雜度為 O(n) 的算法表示其運行時間隨著輸入大小的線性增長。
• 空間復雜度：衡量算法的內存使用量如何隨著輸入大小的變化而變化。例如，空間復雜度為 O(n) 的算法表示其內存使用量隨著輸入大小的線性增長。

圖片

01 O(1) - 恒定時間

運行時間恒定，不隨輸入大小變化。

典型應用

• 通過索引訪問數組中的元素。
• 插入或刪除哈希表中的一個元素（平均）。

02 O(n) - 線性時間

運行時間隨輸入大小線性增加。

典型應用

• 遍歷列表或數組。
• 查找未排序數組中的最大或最小元素。
• 檢查未排序數組中是否存在元素。

03 O(log n) - 對數時間

運行時間隨輸入大小的增加而對數增加。

典型應用

• 排序數組上的二進制搜索。
• 平衡二叉搜索樹（如 AVL 樹、紅黑樹）上的操作。
• 查找二進制堆中最大或最小的元素。

04 O(n^2) - 二次方時間

運行時間隨輸入的大小呈二次方增長。

典型應用

• 簡單的排序算法，如冒泡排序、選擇排序和插入排序。
• 涉及輸入內容嵌套循環的算法（例如，比較所有元素對）。
• 解決某些動態編程問題，如矩陣鏈式乘法的 native 實現。

05 O(n^3) - 立方時間

運行時間隨輸入的大小呈立方增長。

典型應用

• 更復雜的動態編程問題，如 Floyd-Warshall 最短路徑算法的天真實現。
• 使用 native 算法計算兩個密集矩陣的乘法。

06 O(n log n) - 線性時間

運行時間以線性對數方式增長，結合了線性增長和對數增長。

典型應用

• 高效排序算法，如合并排序、快速排序（平均情況）和堆排序。
• 從排序數組構建二叉搜索樹。

07 O(2^n) - 指數時間

輸入每增加一個元素，運行時間就增加一倍。

典型應用

• 將問題分成多個子問題來解決的遞歸算法，例如旅行推銷員問題的 native 解法。
• 利用遞歸解決子集和問題。
• 生成集合的所有子集。

08 O(n!) - 因式分解時間

運行時間隨輸入大小的因子增長。

典型應用

• 排列生成問題。
• 旅行推銷員問題的暴力解法。
• 解決涉及生成集合所有可能排序的問題。

09 O(sqrt(n)) - 平方根時間

運行時間與輸入大小的平方根成比例增長。

典型應用

• 涉及在一定范圍內搜索的算法，如查找 n 以內所有素數的 Eratosthenes 篩法。
• 計算幾何中的某些算法。