Python Data Structure 简明教程
Python - Algorithm Types
必须分析算法的效率和准确性，以对它们进行比较并针对特定方案选择特定算法。进行此分析的过程称为渐近分析。它指的是用数学计算单位计算任何运算的运行时间。
The efficiency and accuracy of algorithms have to be analysed to compare them and choose a specific algorithm for certain scenarios. The process of making this analysis is called Asymptotic analysis. It refers to computing the running time of any operation in mathematical units of computation.
例如，一个运算的运行时间计算为 f(n)，另一个运算的运行时间可能计算为 g(n2)。这意味着第一个运算的运行时间将随着 n 的增加而线性增加，而第二个运算的运行时间在 n 增加时将呈指数增加。类似地，如果 n 非常小，则这两个运算的运行时间将几乎相同。
For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.
通常，算法所需的时间分为以下三种类型−
Usually, the time required by an algorithm falls under three types −
-
Best Case − Minimum time required for program execution.
-
Average Case − Average time required for program execution.
-
Worst Case − Maximum time required for program execution.
Asymptotic Notations
常用的渐进符号来计算算法的运行时间复杂度。
The commonly used asymptotic notations to calculate the running time complexity of an algorithm.
-
Ο Notation
-
Ω Notation
-
θ Notation
Big Oh Notation, Ο
符号 Ο(n) 是表示算法运行时间上限的正式方法。它测量最坏情况时间复杂度或算法可能花费的最长时间来完成。
The notation Ο(n) is the formal way to express the upper bound of an algorithm’s running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.
例如，对于函数 f(n)
For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }Omega Notation, Ω
符号 Ω(n) 是表示算法运行时间下限的正式方法。它测量最佳情况时间复杂度或算法可能花费的最短时间来完成。
The notation Ω(n) is the formal way to express the lower bound of an algorithm’s running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.
例如，对于函数 f(n)
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }