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

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

大 O 符號主要用于表達(dá)以下內(nèi)容：

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

圖片

01 O(1) - 恒定時間

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

典型應(yīng)用

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

02 O(n) - 線性時間

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

典型應(yīng)用

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

03 O(log n) - 對數(shù)時間

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

典型應(yīng)用

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

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

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

典型應(yīng)用

• 簡單的排序算法，如冒泡排序、選擇排序和插入排序。
• 涉及輸入內(nèi)容嵌套循環(huán)的算法（例如，比較所有元素對）。
• 解決某些動態(tài)編程問題，如矩陣鏈?zhǔn)匠朔ǖ?native 實現(xiàn)。

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

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

典型應(yīng)用

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

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

運行時間以線性對數(shù)方式增長，結(jié)合了線性增長和對數(shù)增長。

典型應(yīng)用

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

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

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

典型應(yīng)用

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

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

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

典型應(yīng)用

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

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

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

典型應(yīng)用

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