算法的效率取决于执行该算法所需的时间、存储以及其他资源的数量。算法的效率是借助渐近表示法来衡量的。
一个算法对不同类型的输入来说，可能有不同的性能。随着输入规模的增长，性能会变化。
对算法性能随输入规模量级的变化而产生的变化情况的研究被定义为渐近分析。
你想以正确的方式学习时间复杂度吗？免费报名参加我们的交互式复杂度计算课程吧。
渐近表示法
渐近表示法是一种数学表示法，用于描述当输入趋向于某个特定值或极限值时，算法的运行时间情况。
例如：在冒泡排序中，当输入数组已经是有序的时候，该算法所花费的时间是线性的，也就是说这是它的最佳情况。
但是，当输入数组处于逆序状态时，该算法需要花费最长的时间（呈二次方时间复杂度）来对元素进行排序，也就是说这是它的最坏情况。
当输入数组既不是已排序状态，也不是逆序状态时，那么该算法就会花费平均时间。这些时间长度是用渐近表示法来表示的。
主要有三种渐近表示法：
- 大 O 表示法
- Ω（欧米伽）表示法
- Θ（西塔）表示法
大O表示法
大 O 表示法表示一个算法运行时间的上限。因此，它给出了一个算法的最坏情况复杂度。
O(g(n)) = { f(n): 存在正常数c和n0,对于所有n>=n0都有0<=f(n)<=cg(n) }
上述表达式可以这样描述：如果存在一个正常数c，使得对于足够大的n，函数f(n)的值介于0和c*g(n)之间，那么函数f(n)就属于集合O(g(n))。
对于任意的n值，一个算法的运行时间都不会超过由大O表示法O(g(n))所给出的时间。
由于大O表示法给出了算法的最坏情况运行时间，并且我们总是关注最坏情况的场景，所以它被广泛用于分析算法。
Ω（欧米伽）表示法
Ω（欧米伽）表示法表示一个算法运行时间的下限。因此，它给出了一个算法的最佳情况复杂度。
Ω(g(n)) = { f(n): 存在正常数c和n0,对于所有n>=n0都有0<=cg(n)<=f(n) }
上述表达式可以描述为：若存在一个正常数 c，对于足够大的 n，函数 f (n) 的值大于等于 cg (n)，那么函数 f (n) 就属于集合 Ω(g (n))。 对于任意的 n 值，Ω(g (n)) 给出了算法所需的最短时间。
Θ（西塔）表示法
Θ（西塔）表示法从上下两个方向界定了函数。由于它表示了一个算法运行时间的上限和下限，所以它被用于分析算法的平均情况复杂度。
对于一个函数g(n)，Θ(g(n))由以下关系给出：
Θ(g(n)) = { f(n): 存在正常数c1,c2和n0，对于所有n>=n0都有 0<=c1g(n)<=f(n)<=c2g(n) }
上述表达式可以这样描述：如果存在正常数c1和c2，使得对于足够大的n，函数f(n)能够被夹在c1g(n)和c2g(n)之间，那么函数f(n)就属于集合Θ(g(n))。如果对于所有n≥n0，函数f(n)的值都处于c1g(n)和c2g(n)之间的任何位置，那么就称f(n)是渐近紧确界。
备注（不是原文翻译）
f(n)：代表算法的实际运行时间函数，它描述了随着输入规模的变化，算法执行所花费时间的变化情况
cg(n)：是人为设定用于对比的函数，c是正常数，对g(n)缩放
