数据结构渐近分析

算法的渐近分析，指的是定义它的运行时性能的数学基础/帧。利用渐近分析，我们可以很好地得出一种算法结论：最好的情况，平均情况和最坏的情况。

渐近分析输入的约束，即如果没有输入到算法可以断定在一个恒定的时间工作。而非 “输入” 的其他因素都被认为恒量。

渐近分析是指计算中的数学单元的任何操作的运行时间。例如，一种操作的运行时间被计算为 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. }