大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:

目录
相关文章
|
8月前
|
C#
C#学习相关系列之常用符号介绍
C#学习相关系列之常用符号介绍
|
5月前
数字符号概述
数字符号概述
32 0
|
8月前
|
存储 编译器 C语言
【C语言】求任意两整数的和入门详解
【C语言】求任意两整数的和入门详解
51 0
|
存储 人工智能 编译器
C语言之(有关%d和%u的有关内容,输出方法)(有符号和无符号在内存中的存储情况)(整形无符号数和有符号数是如何进行计算的,整形无符号数和有符号数在循环中的应用举例)
C语言之(有关%d和%u的有关内容,输出方法)(有符号和无符号在内存中的存储情况)(整形无符号数和有符号数是如何进行计算的,整形无符号数和有符号数在循环中的应用举例)
536 0
|
C语言 C++
数字前后加上符号“*”----c代码
数字前后加上符号“*”----c代码
126 0
数字前后加上符号“*”----c代码
|
IDE C# 开发工具
=>符号使用场景
=>符号使用场景
172 0
=>符号使用场景
|
算法 搜索推荐 数据安全/隐私保护
简明解释算法中的大 O 符号
2009年1月28日Arec Barrwin在StackOverflow上提问,“有没有关于大O符号(Big O notation)的简单解释?尽量别用那么正式的定义,用尽可能简单的数学来解释”。在经过众多热心网友的修改更新后,最佳回复的得分已高达 3234 分,详细内容,请见下文。
305 0
简明解释算法中的大 O 符号
|
C++
C++学习009预处理器指令符号 # ## #@ 符号的使用
# ## #@ 符号是预处理器指令符号。
125 0
mathjax符号
mathjax公式 \(\delta\): \delta \(\Delta\): \Delta \(\int\): \int \(\iint\): \iint \(\approx\): \approx \(\theta\): \theta \(\alpha\): \alp...
1183 0