算法的渐进效率分析

算法的效率取决于执行算法所需的时间、存储和其他资源。而要精确的计算算法执行时消耗的资源时非常困难的，而渐进分析法则时分析算法效率的一种方法。。在渐近符号的帮助下测量效率。

对于不同类型的输入，算法可能具有不同的性能。随着输入大小的增加，性能会发生变化。研究算法性能随输入大小阶数的变化而变化的研究被定义为渐近分析。

使用渐进分析法衡量算法的时候，需要用到一些符号，他们被称为渐进符号。

渐近符号

渐近符号是用于描述当输入趋于特定值或极限值时算法的运行时间的数学符号。

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

但是，当输入数组处于反向条件时，算法需要最长时间(二次)来对元素进行排序，即最坏的情况。

当输入数组既没有排序也没有倒序时，则需要平均时间。这些持续时间使用渐近符号表示。

主要有三种渐近符号：

• 大 O 符号
• 欧米茄 符号 Ω
• Theta 符号 θ

Big-O 表示法(O 表示法)

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

当函数的大小只有上界，没有明确下界的时候，则可以使用大 O 表示法。f(n)= O(g(n)) 正式的数学定义：存在正常数 c、n、n0，当 n>n0 的时，对于任意的 f(n) 对符合 0<= f(n)<= c.g(n)。

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

欧米茄符号(Ω-符号)

Omega 表示法表示算法运行时间的下限。因此，它提供了算法的最佳情况复杂度。

当函数的大小只有下界，没有明确的上界的时候，可以使用大 Ω 表示法。f(n)= Ω(g(n)) 正式的数学定义：存在正常数 c、n、n0，当 n>n0 的时，对于任意的 f(n)对符合 0<= c.g(n)<= f(n)。

Theta 表示法(Θ 表示法)

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

算法导论 中是如何描述大 θ 表示法的。

f(n)= θ(c.g(n)) 正式的数学定义：存在正常数 c1、c2、n、n0，当 n>n0 的时，对于任意的 f(n) 对符合 c1.g(n)<= f(n)<= c2.g(n)，c1.g(n)、c2.g(n) 都是渐进正函数(当 n 趋于无穷大的时候，f(n)为正)。