數據結構漸近分析

算法的漸近分析，指的是定義它的運行時性能的數學基礎/幀。利用漸近分析，我們可以很好地得出一種算法結論：最好的情況，平均情況和最壞的情況。

漸近分析輸入的約束，即如果沒有輸入到算法可以斷定在一個恆定的時間工作。而非「輸入」的其他因素都被認爲恆量。

漸近分析是指計算中的數學單元的任何操作的運行時間。例如，一種操作的運行時間被計算爲 f（n），以及用於另一操作它計算爲 g(n2)。這意味着第一操作運行時間線性增加而增加，n 和運行第二操作時間會在 n 增加時成倍增加。同樣地，如果 n 足夠小，那麼兩個操作的運行時間將幾乎相同。

通常情況下，由算法所需要的時間在三種類型 −

漸近表示法

下面是常用的，在計算運行時間的算法的複雜性使用漸近符號。

Ο（n）是表達的上限的算法的運行時間的正式方法。它測量的最壞情況下的時間複雜度和時間的算法可能才能完成最長時間。 For example, for a function例如，對於一個函數f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Ω（n）是表達的下界的算法的運行時間的正式方法。它衡量最好情況下的時間複雜度和時間的算法可能才能完成最佳用量。

例如，對於一個函數 f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

θ（n）表達正式的方式，既下界和上界的算法的運行時間。它被表示爲如下。

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

常量

−

Ο(1)

對數

−

Ο(log n)

線性

−

Ο(n)

n log n

−

Ο(n log n)

二次

−

Ο(n2)

立方

−

Ο(n3)

多項式

−

nΟ(1)

指數

−

2Ο(n)