Python 算法类型
Python 算法类型详细操作教程
必须分析算法的效率和准确性以进行比较,并针对某些情况选择特定的算法。进行此分析的过程称为渐近分析。它是指以数学计算单位计算任何操作的运行时间。例如,一个操作的运行时间计算为f(n),对于另一项操作,它的运行时间可能计算为g(n2)。这意味着第一操作的运行时间将随着n的增加线性增加,而第二操作的运行时间将随着n的增加呈指数增长。同样,如果n很小,则两个操作的运行时间将几乎相同。
通常,算法所需的时间分为以下三种:
最佳情况-程序执行所需的最短时间。
平均情况-程序执行所需的平均时间。
最坏的情况-程序执行所需的最长时间。
渐近符号
以下是常用的渐近符号来计算算法的运行时间复杂度。
Ο表示法
Ω 表示法
θ 表示法
大O复杂度分析
符号Ο(n)是表达算法运行时间上限的正式方法。它测量最坏情况下的时间复杂度或算法可能花费的最长时间。
例如,对于函数f(n)
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
Ο(
f(n)) = {
g(n) : there exists c > 0
and n
0 such that
f(n) ≤ c.
g(n)
for all n > n
0. }
Ω复杂度
Ω(n)表示形式是算法运行时间的下限。它测量最佳情况下的时间复杂度或算法可能花费的最佳时间。
例如,对于函数f(n)
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
Ω(
f(n)) ≥ {
g(n) : there exists c > 0
and n
0 such that
g(n) ≤ c.
f(n)
for all n > n
0. }
θ表示法
θ(n)表示形式是算法运行时间的下限和上限。它表示如下-
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
θ(
f(n)) = {
g(n)
if
and only
if
g(n) = Ο(
f(n))
and
g(n) = Ω(
f(n))
for all n > n
0. }
常见渐近符号
Following is a list of some common asymptotic notations −
constant |
− |
Ο(1) |
logarithmic |
− |
Ο(log n) |
linear |
− |
Ο(n) |
n log n |
− |
Ο(n log n) |
quadratic |
− |
Ο(n2) |
cubic |
− |
Ο(n3) |
polynomial |
− |
nΟ(1) |
exponential |
− |
2Ο(n) |