大O符号基础

简介: 大O符号(Big O notation), 又称渐进符号,是用于描述函数的渐近行为的数学符号。它是指用另一个(通常更简单的)函数来描述一个函数数量级的渐进上界。

大O符号(Big O notation), 又称渐进符号,是用于描述函数的渐近行为的数学符号。它是指用另一个(通常更简单的)函数来描述一个函数数量级的渐进上界。

  • 由德国数论学家保罗·巴赫曼首次引入,并由德国数论学家艾德蒙·朗道推广。
符号 名称
O(1) 常量时间
O(log n) 对数时间
O[(log n)c] 多对数时间
O(n) 线性时间
O(nlog*n) 线性迭代对数时间
O(nlogn) 线性对数时间
O(n2) 平方
O(nc), Integer(c>1) 多项式时间
O(cn) 指数时间
O(n!) 阶乘时间

在n趋于无穷大时,这些函数从上到下增长越来越快。
即在用于描述时间复杂度时,随着问题规模的增大,从上到下所需要消耗的时间越来越多。


相关概念:
多项式时间(Polynomial time)即指一个问题的计算时间m(n) = O(nk ),k为常量值。
数学家有时把“如多项式时间长的算法”视为快速计算。

超多项式时间 即当计算规模足够大,解题时间将大大超过任何多项式时间的问题。


相关符号:
大Ω符号:大O符号表示函数在增长到一定程度时总小于某函数的常数倍,大Ω符号与大O符号正好相反,表示总大于。即:

img_61cc26a694a59ab732672d3a9fb77a22.png

大Θ符号是大O符号和大Ω符号的结合。即:

img_aeb8eed7ac97134f69c380b1c6d8eb12.png

img_773838740d24205f1d0ae102c8071a67.png

References:

目录
相关文章
|
6月前
|
C#
C#学习相关系列之常用符号介绍
C#学习相关系列之常用符号介绍
|
3月前
数字符号概述
数字符号概述
19 0
|
6月前
|
存储 Java 程序员
基本概念【变量和数据类型和运算符、二进制和十进制、十进制转二进制 、二进制转十进制 】(一)-全面详解(学习总结---从入门到深化)
基本概念【变量和数据类型和运算符、二进制和十进制、十进制转二进制 、二进制转十进制 】(一)-全面详解(学习总结---从入门到深化)
216 0
|
存储 人工智能 编译器
C语言之(有关%d和%u的有关内容,输出方法)(有符号和无符号在内存中的存储情况)(整形无符号数和有符号数是如何进行计算的,整形无符号数和有符号数在循环中的应用举例)
C语言之(有关%d和%u的有关内容,输出方法)(有符号和无符号在内存中的存储情况)(整形无符号数和有符号数是如何进行计算的,整形无符号数和有符号数在循环中的应用举例)
467 0
|
算法 C语言
10(可回看)【C语言 & 趣味算法】数制转换(常见,二进制、八进制、十进制、十六进制之间任意转换)
10(可回看)【C语言 & 趣味算法】数制转换(常见,二进制、八进制、十进制、十六进制之间任意转换)
10(可回看)【C语言 & 趣味算法】数制转换(常见,二进制、八进制、十进制、十六进制之间任意转换)
|
算法 搜索推荐 数据安全/隐私保护
简明解释算法中的大 O 符号
2009年1月28日Arec Barrwin在StackOverflow上提问,“有没有关于大O符号(Big O notation)的简单解释?尽量别用那么正式的定义,用尽可能简单的数学来解释”。在经过众多热心网友的修改更新后,最佳回复的得分已高达 3234 分,详细内容,请见下文。
292 0
简明解释算法中的大 O 符号
特殊符号大全(建议收藏_复制着用_数学符号最下面)(4)
特殊符号大全(建议收藏_复制着用_数学符号最下面)(4)
7353 0
特殊符号大全(建议收藏_复制着用_数学符号最下面)(2)
特殊符号大全(建议收藏_复制着用_数学符号最下面)(2)
405 0
特殊符号大全(建议收藏_复制着用_数学符号最下面)(1)
特殊符号大全(建议收藏_复制着用_数学符号最下面)(1)
436 0
特殊符号大全(建议收藏_复制着用_数学符号最下面)(3)
特殊符号大全(建议收藏_复制着用_数学符号最下面)(3)
262 0