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

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

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

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

圖片

01 O(1) - 恒定時(shí)間

運(yùn)行時(shí)間恒定，不隨輸入大小變化。

典型應(yīng)用

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

02 O(n) - 線性時(shí)間

運(yùn)行時(shí)間隨輸入大小線性增加。

典型應(yīng)用

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

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

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

典型應(yīng)用

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

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

運(yùn)行時(shí)間隨輸入的大小呈二次方增長。

典型應(yīng)用

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

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

運(yùn)行時(shí)間隨輸入的大小呈立方增長。

典型應(yīng)用

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

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

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

典型應(yīng)用

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

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

輸入每增加一個(gè)元素，運(yùn)行時(shí)間就增加一倍。

典型應(yīng)用

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

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

運(yùn)行時(shí)間隨輸入大小的因子增長。

典型應(yīng)用

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

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

運(yùn)行時(shí)間與輸入大小的平方根成比例增長。

典型應(yīng)用

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