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）

下一章：Python 算法类

算法是明确的步骤，应该通过处理零个或多个输入给我们一个明确的输出。这导致了设计和编写算法的许多方法。据观察，大多数算法可以分为以下几类。贪婪算法贪婪算法试图找到一个局部最优解，这可能最终导致全球优化的解决方 ...

上一章：Python 图算法

下一章：Python 算法类