算法分析:大O符号/大Ω符号/大Θ符号/小o符号/小w符号

article/2025/8/22 10:48:46

感谢作者分享,原文链接:http://blog.csdn.net/u012816041/article/details/49888631

大O,渐进表示法,接下来我尝试用最简单的方式进行说明。

学习算法我经常听到这个词汇,我一开始很难理解,什么鬼?其实简单的说,就是描述一个算法的好坏词。

大O,可以认为它的含义是“order of”(大约是)。

简单列举几个,当人们形容:

某个算法的时间复杂度是O(1),就说明这是一个优秀的算法。

某个算法的时间复杂度是O(logn),就说明这是一个良好的算法。

某个算法的时间复杂度是O(n),就说明这个算法还不错。

某个算法的时间复杂度是O(n2),就说明这个算法差一些了。

上面那些记住后,至少让你,听到这个词后不会呆。。额。。


其实知其然不知其所以然是很可怕的,不过上面内容,起码保证了过一段时间不会一无所知。接下来是具体的数学分析和其他的一些表示法,直接上维基百科了。


大O符号

注:“order”在全文中被译为“”,也可以另译为“数量级”。

大O符号英语:Big O notation)是用于描述函数渐近行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。

大O符号是由德国数论学家保罗·巴赫曼(Paul Bachmann)在其1892年的著作《解析数论》(Analytische Zahlentheorie)首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道(Edmund Landau)的著作中才推广的,因此它有时又称为朗道符号(Landau symbols)。代表“order of ...”(……阶)的大O,最初是一个大写的希腊字母'Ο'(omicron),现今用的是大写拉丁字母‘O’,但从来不是阿拉伯数字‘0’

目录

    [隐藏] 
  • 1使用
    • 1.1无穷大渐近
    • 1.2无穷小渐近
  • 2形式化定义
  • 3常用的函数阶
  • 4一些相关的渐近符号
  • 5注意
  • 6参看
  • 7参考资料

使用

这个符号有两种形式上很接近但迥然不同的使用方法:无穷大渐近与无穷小渐近。然而这个区别只是在运用中的而不是原则上的——除了对函数自变量的一些不同的限定, “大O”的形式定义在两种情况下都是相同的。[来源请求]

无穷大渐近

大O符号在分析算法效率的时候非常有用。举个例子,解决一个规模为n的问题所花费的时间(或者所需步骤的数目)可以表示为:T(n)=4n^2-2n+2。当n增大时,n^2项将开始占主导地位,而其他各项可以被忽略。 举例说明:当n=5004n^2项是 2n项的1000倍大,因此在大多数场合下,省略后者对表达式的值的影响将是可以忽略不计的。

进一步看,如果我们与任一其他级的表达式比较,n^2项的系数也是无关紧要的。例如:一个包含n^3n^2项的表达式,即使 T(n)=1,000,000\cdot n^2,假定 U(n)=n^3,一旦n增长到大于1,000,000,后者就会一直超越前者(T(1,000,000)=1,000,000^3=U(1,000,000))。

这样,大O符号就记下剩余的部分,写作:

T(n)\in\Omicron(n^2)

T(n)=\Omicron(n^2)

并且我们就说该算法具有n^2阶(平方阶)的时间复杂度。

无穷小渐近

大O也可以用来描述数学函数估计中的误差项。例如e^x的泰勒展开:

e^x=1+x+\frac{x^2}{2}+\hbox{O}(x^3)\qquadx \to 0

这表示,如果x足够接近于0,那么误差e^x - \left(1 + x + \frac{x^2}{2}\right)的绝对值小于x^3的某一常数倍。

形式化定义

给定两正值函数fg,定义:

f(n)=\Omicron(g(n)),条件为:存在正实数cN,使得对于所有的n \geq N,有|f(n)| \leq |cg(n)|

上述的定义表明,当n足够大,大过一个特定的N时,且存在一个正数c,使得|f|不大于|cg|,则fg\Omicron表示。fg的关系可以理解为g(n)f(n)的一个上界,也可以理解为f最终至多增涨的速度与g一样快,但不会超过g的增涨速度。

常用的函数阶

下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于n趋近于无穷大的情况下,增长得慢的函数列在上面。c是一个任意常数。

符号 名称
\Omicron(1)\!常数(阶,下同)
\Omicron(\log n)\!对数
\Omicron[(\log n)^c]\!多对数
\Omicron(n)\!线性,次线性
\Omicron(n\log^*n)\!\log^*n为迭代对数
\Omicron(n \log n)\!线性对数,或对数线性、拟线性、超线性
\Omicron( n^2)\!平方
\Omicron(n^c), \operatorname{Integer}(c>1)多项式,有时叫作“代数”(阶)
\Omicron(c^n)\!指数,有时叫作“几何”(阶)
\Omicron(n!)\!阶乘,有时叫做“组合”(阶)

一些相关的渐近符号

大O是最经常使用的比较函数的渐近符号。

符号 定义
 f(n)=\Omicron (g(n))渐近上限
f(n)=o(g(n))asymptotically negligible(\lim{} \frac{f(n)}{g(n)} = 0
 f(n)=\Omega(g(n))渐近下限 (当且仅当 g(n) = \Omicron(f(n))
 f(n) = \omega (g(n)) asymptotically dominant(当且仅当g(n)=o(f(n))
 f(n) = \Theta(g(n))asymptotically tight bound(当且仅当f(n) = \Omicron(g(n))f(n)=\Omega(g(n))

注意

大O符号经常被误用:有的作者可能会使用大O符号表达大Θ符号的含义。因此在看到大O符号时应首先确定其是否为误用。

大Ω符号

大Θ符号

Θ符号是大O符号和大Ω符号的结合。即:f(\nu)=\Theta[g(\nu)]\!\begin{cases}f(\nu)=\Omicron[g(\nu)]\\f(\nu)=\Omega[g(\nu)]\end{cases}

这一符号首先由高德纳于1970年提出[1]

注意

大Θ符号经常被误用;有的作者可能会使用大O符号表达大Θ符号的含义。因此在看到大O符号时应首先确定其是否为误用。


我发现读完维基百科还是有一些不清晰的地方,或者不好理解的地方,再加上这些。

设函数f ( n )代表某一算法在输入大小为n的情况下的工作量(效率),则在n趋向很大的时候,我们将f (n)与另一行为已知的函数g(n)进行比较:

1)如果0,则称f (n)在数量级上严格小于g(n),记为f (n)=o( g(n))。

2)如果,则称f (n)在数量级上严格大于g(n),记为f (n)=w( g(n))。

3)如果c,这里c为非0常数,则称f (n)在数量级上等于g(n),即f (n)和g(n)是同一个数量级的函数,记为:f (n)=Θ( g(n))。

4)如果f (n)在数量级上小于或等于g(n),则记为f (n)=O( g(n))。

5)如果f(n)在数量级上大于或等于g(n),则记为f (n)=Ω( g(n))。

这里我们假定f (n),g (n)是非负单调的,且极限存在。如果这个极限不存在,则无法对f (n)和g (n)进行比较。在进行此种计算时,一个经常用到的技术是洛必达(L'Hopital)法则。该法则由17世纪法国数学家Guillaume de L'Hopital发现(也有人认为是瑞士数学家Johann Bernoulli发现的)。该法则声称,两个函数的比率极限等于两个函数的导数的比率极限,这里当然假定两个函数的导数比率的极限存在,即有:


 

有了这个定义,就可以对素性测试的两个算法进行比较了。


http://chatgpt.dhexx.cn/article/cLaORFcE.shtml

相关文章

算法分析—大O、大Ω、大θ

前言 在算法的学习中,最开始便是要学习算法的分析。学习算法分析时,我们便会接触到这么几个符号:大O、大Ω、大θ,常常让人难以理解。 在通常的算法分析时,我们可以明白,在输入规模较小,各种算…

算法分析——大O标记法

目录 一. 运行时间 二. 大O 表示法 2.1 示例 三. 总结 五. 扩展 一. 运行时间 每次介绍算法时,我们都将讨论其运行时间。一般而言,应选择效率最高的算法,以最大限度地减少运行时间或占用空间。 可是,如果代码都还没有运行&a…

Oracle数据库查询语句

1 oracle数据库查询表的所有数据–select * from 表名;(* 代表所有) 2 oracle数据库查询表中指定字段的值–select 字段名1,字段名2,……from 表名; 3 oracle数据库往表中添加数据信息–(添加信息使用inser…

Access数据库的查询

内容很简单,我搭建access数据库就是为了简单测试access语句的对错,以及学习access数据库的语法。 1.打开access数据库。 2.主页->空数据库 3.创建数据 4.创建->查询设计 5.【显示表】中的【表】【查询】【两者都有】,都可以。点击添加…

数据库查询语句SQL中like、%、-的区别

数据库查询语句SQL中like、%、-的区别 数据库查询语句SQL中like、%、-的区别 %百分号通配符:表示任何字符出现任意次数(可以是0次) SQL 语句选取 name 以字母 "k" 结尾的所有客户: SELECT * FROM Websites WHERE name LIKE %k; 执行输出结果: 下划线通配符:表示…

使用oracle数据库分页查询语句,各种数据库的分页查询语句

各种数据库的分页查询语句 1.oracle数据库分页select * from (select a.*,rownum rc from 表名 where rownum=endrow) a where a.rc=startrow2.DB2数据库分页Select * from (select rownumber() over() as rc,a.* from (select * from 表名 order by 列名) as 各种数据库的分页…

解决数据库查询语句where条件为空查询全部数据,不为空按照条件查询

问题:在用查询语句查询电影类型,电影年代,电影区域的时候,要返回全部的数据,就是where条件为空,返回所有的数据 解决:select * from 表 where (字段条件 or 条件‘’) 代码: const …

数据库内外联接查询语句

建立如下表并插入数据: create table s(sid varchar2(10) primary key,sname varchar2(50),sage number(30));insert into s values(111,小红,20);insert into s values(222,小红,20);insert into s values(333,小红,20);insert into s values(555,小红,20);create…

SQL Server数据库的查询语句

select version; #查询数据库的版本 select servername; #查询服务名 select host_name(); #查询主机名,如果是用navicat远程连接的话,主机名是本地的名字 select db_name(); #查询当前数据库名 select db_name(1); #查询第一个数据库名 select db_name(…

数据库去重语句整理

示例数据 Test表中有id和name两个字段,id各不相同,name有重复。 现在需要去除重复的数据,只保留重复的里面id最大的数据。 一、去重语句一(通用型): SELECT * FROM test c where c.id in( SELECT b.id from test a,test b wher…

数据库查询中的in语句

数据库查询中的in语句 在数据库中也有运算符&#xff0c;比如<、>、、之类的&#xff0c;还有一些or、and之类的&#xff0c;下面我们来学习关于in语句的方法&#xff0c;in在数据库中到底起怎样的作用&#xff1f; 如上图&#xff0c;我通过where语句限制年龄&#xff0…

数据库查询语句(二)-条件查询

文章目录 前言一、单条件查询二、多条件查询 前言 1. 熟练掌握where子句各类运算符的使用 2. 熟练掌握多条件查询and、or的使用 一、单条件查询 在SQL中&#xff0c;insert、update、delete和select后面都能带where子句&#xff0c;用于插入、修改、删除或查询指定条件的记…

数据库查询语句中的排序

1.排序查询语法 排序查询语法&#xff1a; select * from 表名 order by 列1 asc|desc [,列2 asc|desc,...]语法说明&#xff1a; 先按照列1进行排序&#xff0c;如果列1的值相同&#xff0c;则按照列2排序&#xff0c;以此类推asc从小到大排序&#xff0c;即升序desc从大到…

C# 数据库查询语句1

C# 数据库查询语句1作者&#xff1a;陈钰桃 撰写时间&#xff1a;2022年3月27日第1节. 查询数据 数据库表是存储数据库中所有数据的对象。 在表中&#xff0c;数据按行和列格式逻辑组织&#xff0c;类似于电子表格(Excel)。在表中&#xff0c;每行代表一个唯一记录&#xff0c;…

数据库基础之查询语句

mysql三范式&#xff1a; 第一范式(确保每列保持原子性)【属性不可分】 第二范式(确保表中的每列都和主键相关)【符合第一范式&#xff0c;同时非主属性完全依赖于主键】 第三范式(确保每列都和主键列直接相关,而不是间接相关)【符合2NF&#xff0c;并且消除传递依赖】 前言 …

数据库的查询语句

目录 一 . 基本查询 1. 查询所有数据 2.查询部分字段 3. 起字段别名 4. 拓展 二 . 条件查询 三 . 模糊查询 四 . 范围查询 五 . 为空查询 六 . 排序 七 . 聚合函数 八 . 分组 九 . 分页查询 练习模板 一 . 基本查询 1. 查询所有数据 select * from goods; 2.查…

深度学习-深度卷积神经网络发展

AlexNet网络 现代意义上的深度卷积神经网络起源于AlexNet网络&#xff0c;它是深度卷积神经网络的鼻祖。这个网络相比之前的卷积网络最显著的特点是层次加深&#xff0c;参数规模变大。网络结构如下图所示&#xff1a; 这个网络有5个卷积层&#xff0c;它们中的一部分后面接着m…

什么是深度卷积神经网络,基于深度卷积神经网络

卷积神经网络算法是什么&#xff1f; 一维构筑、二维构筑、全卷积构筑。 卷积神经网络&#xff08;ConvolutionalNeuralNetworks,CNN&#xff09;是一类包含卷积计算且具有深度结构的前馈神经网络&#xff08;FeedforwardNeuralNetworks&#xff09;&#xff0c;是深度学习&a…

经典卷积和深度卷积的神经网络

文章目录 LeNet网络AlexNet深度卷积神经网络 (AlexNet)VGGNIN(网络中的概念)含并行连接的网络GoogLeNet / Inception V3批量 归一化一些B站评论区大佬讨论残差网络ResNetResNet为什么能训练一千层暂时浅过一遍,不求每个部分都理解很深度,后面通过复现项目来加深理解。 这里…

深度学习--卷积神经网络

目录 &#xff08;一&#xff09;输入层&#xff08;Input Layer&#xff09; &#xff08;二&#xff09;卷积层&#xff08;Convolution Layer&#xff09; &#xff08;三&#xff09;激活层&#xff08;Activation Layer&#xff09; &#xff08;四&#xff09;池化层…