Python Data Structure 简明教程

Python - Algorithm Types

必须分析算法的效率和准确性，以对它们进行比较并针对特定方案选择特定算法。进行此分析的过程称为渐近分析。它指的是用数学计算单位计算任何运算的运行时间。

例如，一个运算的运行时间计算为 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. }

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

constant

−

Ο(1)

logarithmic

−

Ο(log n)

linear

−

Ο(n)

n log

−

Ο(n log n)

quadratic

−

Ο(n2)

cubic

−

Ο(n3)

polynomial

−

nΟ(1)

exponential

−

2Ο(n)