渐进分析：大O表示法及更多

算法的效率取决于执行算法所需的时间、存储和其他资源量。效率通过渐进表示法来衡量。

算法对于不同类型的输入可能没有相同的性能。随着输入尺寸的增加，性能会发生变化。

研究算法性能随输入尺寸顺序变化的研究称为渐进分析。

您想正确学习时间复杂度吗？ 免费注册我们的互动式复杂度计算课程。

渐近表示法

渐进表示法是用来描述当输入趋向于某个特定值或极限值时算法运行时间的数学表示法。

例如：在冒泡排序中，当输入数组已排序时，算法所需时间是线性的，即最好情况。

但是，当输入数组是逆序时，算法需要最长的时间（二次方）来排序元素，即最坏情况。

当输入数组既不是有序也不是逆序时，它需要平均时间。这些时间长度用渐进表示法表示。

主要有三种渐进表示法：

• 大O表示法
• 欧米茄表示法
• 西塔表示法

大O表示法（O-notation）

大O表示法表示算法运行时间的上限。因此，它给出了算法的最坏情况复杂度。

O(g(n)) = { f(n): there exist positive constants c and n0
            such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

上述表达式可以描述为，当存在一个正的常数c，使得对于足够大的n，f(n)介于0和cg(n)之间时，则称函数f(n)属于集合O(g(n))。

对于任何n值，算法的运行时间都不会超过O(g(n))提供的时间。

由于它给出了算法的最坏运行时间，因此被广泛用于分析算法，因为我们总是对最坏情况场景感兴趣。

欧米茄表示法（Ω-notation）

欧米茄表示法表示算法运行时间的下限。因此，它给出了算法的最好情况复杂度。

Ω(g(n)) = { f(n): there exist positive constants c and n0 
            such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

上述表达式可以描述为，当存在一个正的常数c，使得对于足够大的n，f(n)大于cg(n)时，则称函数f(n)属于集合Ω(g(n))。

对于任何n值，算法所需的最小时间由欧米茄Ω(g(n))给出。

西塔表示法（Θ-notation）

西塔表示法从上方和下方包围函数。由于它表示算法运行时间的上限和下限，因此用于分析算法的平均情况复杂度。

对于函数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，使得对于足够大的n，f(n)可以被夹在c1g(n)和c2g(n)之间时，则称函数f(n)属于集合Θ(g(n))。

如果函数f(n)对于所有n ≥ n0都位于c1g(n)和c2g(n)之间，则称f(n)是渐进紧界。

您想正确学习时间复杂度吗？ 免费注册我们的互动式复杂度计算课程。