Big-O Notation

必须分析算法的效率和准确性以比较它们并为某些场景选择特定算法。 进行此分析的过程称为渐近分析。 它指的是以数学计算单位计算任何操作的运行时间。 例如，一个操作的运行时间计算为f（n），并且可以用于另一个操作，其计算为g（n2）。 这意味着第一操作运行时间将随着n的增加而线性增加，并且当n增加时第二操作的运行时间将指数地增加。 类似地，如果n非常小，则两个操作的运行时间几乎相同。

通常，算法所需的时间分为三种类型 -

• 最佳案例 - 程序执行所需的最短时间。
• 平均情况 - 程序执行所需的平均时间。
• 最坏情况 - 程序执行所需的最长时间。

渐近符号

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

• Ο符号
• Ω表示法
• θ表示法

大哦符号，Ο

符号Ο（n）是表示算法运行时间上限的正式方式。 它测量最坏情况下的时间复杂度或算法可能需要完成的最长时间。

例如，对于函数f (n)

Ο(<i>f</i>(n)) = { <i>g</i>(n) : there exists c > 0 and n<sub>0</sub> such that <i>f</i>(n) ≤ c.<i>g</i>(n) for all n > n<sub>0</sub>. }

Omega表示法，Ω

符号Ω（n）是表示算法运行时间下限的正式方式。 它测量最佳案例时间复杂度或算法可能需要完成的最佳时间量。

例如，对于函数f (n)

Ω(<i>f</i>(n)) ≥ { <i>g</i>(n) : there exists c > 0 and n<sub>0</sub> such that <i>g</i>(n) ≤ c.<i>f</i>(n) for all n > n<sub>0</sub>. }

Theta Notation，θ

符号θ（n）是表示算法运行时间的下限和上限的形式方式。 它表示如下 -

θ(<i>f</i>(n)) = { <i>g</i>(n) if and only if <i>g</i>(n) =  Ο(<i>f</i>(n)) and <i>g</i>(n) = Ω(<i>f</i>(n)) for all n > n<sub>0</sub>. }

常见的渐近符号

以下列出了一些常见的渐近符号 -