Python - 大O符号


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

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

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

渐近符号

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

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

大O符号

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

大O符号

例如,对于函数 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)是表达算法运行时间的下限和上限的形式化方式。它表示如下 -

Theta符号

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

常用的渐近符号

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

不变 \- Ο(1)
对数的 \- Ο(log n)
线性 \- Ο(n)的
nlogn \- Ο(n log n)
二次 \- Ο(n 2)
立方体 \- Ο(n 3)
多项式 \- Ñ Ο(1)
指数 \- 2 (n)