Python语言基础
Python语言进阶
Python数据结构

Python 算法类型

Python 算法类型详细操作教程
必须分析算法的效率和准确性以进行比较,并针对某些情况选择特定的算法。进行此分析的过程称为渐近分析。它是指以数学计算单位计算任何操作的运行时间。例如,一个操作的运行时间计算为f(n),对于另一项操作,它的运行时间可能计算为g(n2)。这意味着第一操作的运行时间将随着n的增加线性增加,而第二操作的运行时间将随着n的增加呈指数增长。同样,如果n很小,则两个操作的运行时间将几乎相同。
通常,算法所需的时间分为以下三种:
最佳情况-程序执行所需的最短时间。 平均情况-程序执行所需的平均时间。 最坏的情况-程序执行所需的最长时间。

渐近符号

以下是常用的渐近符号来计算算法的运行时间复杂度。
Ο表示法 Ω 表示法 θ 表示法

大O复杂度分析

符号Ο(n)是表达算法运行时间上限的正式方法。它测量最坏情况下的时间复杂度或算法可能花费的最长时间。
大O复杂度
例如,对于函数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)表示形式是算法运行时间的下限和上限。它表示如下-
Theta Notation
# 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)
昵称: 邮箱:
Copyright © 2022 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4