Python - 算法类型

简述

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

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

通常，算法所需的时间分为三种类型 -
- Best Case− 程序执行所需的最短时间。
- Average Case− 程序执行所需的平均时间。
- Worst Case− 程序执行所需的最长时间。
渐近符号

常用的渐近符号来计算算法的运行时间复杂度。
- 符号
- Ω 符号
- θ 符号
O符号，Ο

符号 Ο(n) 是表示算法运行时间上限的正式方式。它测量最坏情况的时间复杂度或算法可能完成的最长时间。

例如，对于一个函数f(n)
```
Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }
```
欧米茄符号，Ω

符号 Ω(n) 是表示算法运行时间下限的正式方式。它测量最佳情况时间复杂度或算法可能完成的最佳时间量。

例如，对于一个函数f(n)
```
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }
```
Theta 表示法，θ

符号 θ(n) 是表示算法运行时间的下限和上限的正式方式。它表示如下 -
```
θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }
```
常用渐近符号

下面提到了一些常见的渐近符号列表 -

常数级 − Ο (1)

对数 − Ο (log n)

线性的 − Ο (n)

对数 − Ο (n log n)

二次方 − Ο (n ² )

立方 − Ο (n ³ )

多项式 − Ο ⁽¹⁾

指数 − 2Ο ⁽ⁿ⁾

常数级	−	Ο (1)
对数	−	Ο (log n)
线性的	−	Ο (n)
对数	−	Ο (n log n)
二次方	−	Ο (n ² )
立方	−	Ο (n ³ )
多项式	−	Ο ⁽¹⁾
指数	−	2Ο ⁽ⁿ⁾

Python - 算法类型

简述

渐近符号

O符号，Ο

欧米茄符号，Ω

Theta 表示法，θ

常用渐近符号