# 漸近分析 > 原文： [https://www.programiz.com/dsa/asymptotic-notations](https://www.programiz.com/dsa/asymptotic-notations) #### 在本教程中，您將學習什么是漸近符號。 此外，您還將了解大 O 表示法，Theta 表示法和 Omega 表示法。 算法的效率取決于執行算法所需的時間，存儲空間和其他資源。 借助漸近符號來測量效率。 對于不同類型的輸入，算法可能不會具有相同的性能。 隨著輸入大小的增加，性能將會改變。 將算法性能隨輸入大小順序的變化而進行的研究定義為漸近分析。 * * * ## 漸近符號 漸進符號是當輸入趨于特定值或極限值時用于描述算法運行時間的數學符號。 例如：在冒泡排序中，當輸入數組已經排序時，算法花費的時間是線性的，即最佳情況。 但是，當輸入數組處于反向條件時，該算法將花費最大時間（二次）對元素進行排序，即最壞的情況。 當輸入數組既未排序也不反向時，則需要平均時間。 這些持續時間使用漸近符號表示。 主要有三種漸近符號：Theta 符號，Omega 符號和大 O 符號。 * * * ## Theta 表示法（Θ 表示法） Theta 表示法從上方和下方將函數括起來。 由于它代表算法運行時間的上限和下限，因此可用于分析算法的平均用例復雜度。  Theta 將函數限制在常數因子之內 對于函數`g(n)`，`Θ(g(n))`由以下關系式給出： ``` Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 } ``` 如果存在正常數`c1`和`c2`，使得可以將其夾在`c1g(n)`和`c2g(n)`之間，則對于足夠大的`n`，可以將上述表達式描述為函數`f(n)`屬于集合`Θ(g(n))`。 如果對于所有`n ≥ n0`，函數`f(n)`位于`c1g(n)`和`c2 > g(n)`之間，則`f(n)`漸近嚴格。 * * * ## 大 O 表示法（O 表示法） 大 O 表示法表示算法運行時間的上限。 因此，它給出了算法的最壞情況的復雜度。  大 O 給出函數的上限 ``` O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 } ``` 對于存在足夠大的`n`的情況，如果存在正常數`c`使得其位于`0`和`cg(n)`之間，則上述表達式可以被描述為函數`f(n)`屬于集合`O(g(n))`。 對于`n`的任何值，算法的運行時間不會與`O(g(n))`提供的時間交叉。 由于它給出了算法的最壞情況下的運行時間，因此它被廣泛用于分析算法，因為我們一直對最壞情況下的場景感興趣。 * * * ## Ω 表示法（Ω表示法） Ω 表示算法運行時間的下限。 因此，它提供了算法的最佳情況復雜度。  Ω 給出函數的下限 ``` Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 } ``` 如果存在足夠大的`n`，如果存在正常數`c`使得它位于`cg(n)`之上，則上述表達式可以描述為函數`f(n)`屬于集合`Ω(g(n))`。 對于`n`的任何值，算法所需的最短時間由 Omega `Ω(g(n))`給出。