Python数据结构 算法类型

必须对算法的效率和准确性进行分析，以便对它们进行比较，并为某些情况选择一种特定的算法。进行这种分析的过程称为渐近分析。它指的是以数学计算单位计算任何操作的运行时间。

例如，一个操作的运行时间被计算为f(n)，而对于另一个操作，它可能被计算为g(n2)。这意味着第一个操作的运行时间将随着n的增加而线性增加，而第二个操作的运行时间将在n增加时以指数形式增加。同样地，如果n明显小，两个操作的运行时间将几乎相同。

通常情况下，一个算法所需的时间分为三种类型–

• 最佳情况 – 程序执行所需的最小时间。

• 平均情况– 程序执行所需的平均时间。

• 最坏情况- -程序执行所需的最大时间。

渐进式符号

常用的渐进式符号来计算算法的运行时间复杂性。

• Ο记号

• Ω符号

• θ记数法

大噢记号，Ο

符号Ο(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. }

θ记号，θ

符号θ(n)是表达算法运行时间的下限和上限的正式方式。它的表示方法如下

θ( _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)
n log n	-	Ο(n log n)
二次方	-	Ο(n2 )
三次	-	Ο(n3 )
多项式	-	n Ο(1 )
指数	-	2 Ο(n )