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. }

Theta 符号, θ

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

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

通用渐近符号

下面列出了一些常见的渐近符号 −