資料結構漸近分析

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

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

漸近分析是指計算中的數學單元的任何操作的執行時間。例如，一種操作的執行時間被計算為 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. }