数据结构 - 渐近分析

算法的渐近分析是指定义其运行时性能的数学边界/框架.使用渐近分析，我们可以很好地得出算法的最佳情况，平均情况和最坏情况.

渐近分析是输入约束，即，如果算法没有输入，结论是在一个恒定的时间内工作.除了"输入"之外，所有其他因素都被认为是常数.

渐近分析是指以数学计算单位计算任何操作的运行时间.例如，一个操作的运行时间计算为 f (n)，并且可以用于另一个操作，它被计算为 g (n ² ).这意味着第一次操作运行时间将随着 n 的增加而线性增加，并且当 n 增加时，第二次操作的运行时间将呈指数增加.同样，如果 n 非常小，两个操作的运行时间几乎相同.

通常，算法所需的时间属于三种类型 :

• 最佳案例 : 程序执行所需的最短时间.

• 平均情况 : 程序执行所需的平均时间.

• 最坏情况 : 程序执行所需的最长时间.

渐近符号

以下是常用的渐近符号计算算法的运行时间复杂度.

• O符号

• ω符号

• Θ符号

1. 渐近紧确界记号:Θ（big-theta）

2. 渐近上界记号 :O(big-oh)

3. 渐近下界记号 :Ω(big-omege)

4. 非渐近紧确上界:o(小-oh)

5. 非渐近紧确下界:ω(小-omege)

6. 渐近记号Θ、Ο、o、Ω、ω关系

Big Oh表示法，O

符号和O(n)是正式的表达方式算法运行时间的上限.它测量最坏情况下的时间复杂度或算法可能需要花费的最长时间.

例如，对于函数 f (n)

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

Omega Notation，O

符号和O(n)是表达低级的正式方式算法运行时间的界限.它衡量最佳案例时间复杂度或算法可能需要完成的最佳时间.

例如，对于函数 f (n)

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

Theta Notation，θ

符号θ(n)是表达两者的正式方式算术运行时间的下限和上限.它表示如下 :

 
Θ(f(n)) = { g(n) if and only if g(n) = O(f(n)) and g(n) = O(f(n)) fo > n0. } }

常见渐近符号

以下是一些常见渐近符号的列表 :

constant	:	O(1)
logarithmic	:	O(log n)
linear	:	O(n)
n log n	:	O(n log n)
quadratic	:	O(n 2 )
cubic	:	O(n 3 )
polynomial	:	n O(1)
exponential	:	2 O(n)