Python - 大O符号

必须分析算法的效率和准确性，以便对它们进行比较，并为特定场景选择特定的算法。进行这种分析的过程称为渐近分析。它是指以数学计算单位计算任何操作的运行时间。例如，一个操作的运行时间被计算为f（n），并且可能针对另一个操作被计算为g（n2）。这意味着第一次运行时间将随着n的增加而线性增加，第二次运行的运行时间将随着n的增加呈指数增长。同样，如果n很小，两个操作的运行时间将几乎相同。

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

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

渐近符号

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

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

大O符号

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

例如，对于函数 f （n）

Ο( _f_ (n)) = { _g_ (n) : there exists c > 0 and n0 such that _f_ (n) ≤ c. _g_ (n) for all n > n0. }

欧米茄符号Ω

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

例如，对于函数 f （n）

Ω( _f_ (n)) ≥ { _g_ (n) : there exists c > 0 and n0 such that _g_ (n) ≤ c. _f_ (n) for all n > n0. }

Theta符号θ

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

θ( _f_ (n)) = { _g_ (n) if and only if _g_ (n) =  Ο( _f_ (n)) and _g_ (n) = Ω( _f_ (n)) for all n > n0. }

常用的渐近符号

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