大O符号

关平藏书 2017-07-31

展开全文

大O符号的示例?F（X） ∈O（克（X）），其存在? > 0（例如，c ^ = 1）和X ₀（例如，X ₀ = 5），使得?F（X） ≤ ? 克（X）每当X ≥ X ₀。

大O表示法是描述当参数趋向于特定值或无穷大时函数的限制行为的数学符号。它是保罗·巴赫曼（Paul Bachmann）^[1]埃德蒙·兰多（Edmund Landau）^[2]等人发明的一个符号家族的成员，统称为巴赫曼 - 兰多（Bachmann-Landau）符号或渐近符号。

在计算机科学中，大O符号被用于根据输入大小的增长来运行时间或空间要求如何增长来对算法进行分类。^[3]在分析数理论中，大O表示法通常用于表达对算术函数和更好理解的近似之间的差异的约束; 这个差异的一个着名的例子就是素数定理的余数。

大O符号根据其增长率来表征功能：具有相同增长率的不同功能可以使用相同的O符号表示。

使用字母O，因为函数的增长率也被称为函数的顺序。在大O符号方面的功能描述通常仅提供功能增长率的上限。与大O符号相关联的是使用符号o，Ω，ω和Θ来描述渐近增长率的其他种类的边界的几个相关符号。

大O表示法也用于许多其他领域，以提供类似的估计。

内容

[ 隐藏 ]

1 正式定义
2 示例
3 使用

3.1 无限渐近
3.2 无穷小渐近

4 属性

4.1 产品
4.2 总计
4.3 乘以常数

5 多个变量
6 符号事项

6.2.1 示例

6.1 等号
6.2 其他算术运算符
6.3 多重用法

7 共同职能的命令
8 相关渐近符号

8.2.1 Hardy-Littlewood定义
8.2.2 Knuth定义

8.2.1.1 简单的例子

8.1 Little-o符号
8.2 大欧米茄符号
8.3 巴赫曼兰登符号系列
8.4 用于计算机科学
8.5 其他符号
8.6 扩展到巴赫曼兰登符号

9 概括和相关用法
10 历史（Bachmann-Landau，Hardy和Vinogradov符号）
11 另见
12 参考文献和注释
13 进一步阅读
14 外部链接

正式的定义[ 编辑]

令f和g是在实数的某个子集上定义的两个函数。一个写

${\ displaystyle f（x）= O（g（x））{\ text {as}} x \ to \ infty}$

当且仅当存在正常数M使得对于所有足够大的x值，f（x）的绝对值至多为M乘以g（x）的绝对值。也就是说，当且仅当存在正实数M和实数x _0时，f（x）= O（g（x）），使得

${\ displaystyle | f（x）| \ leq \; M | g（x）| {\ text {for all}} x \ geq x_ {0}}$ 。

在许多情况下，假设我们对增长率感兴趣，因为变量x变为无限远，而且一个更简单的说

${\ displaystyle f（x）= O（g（x））}$ 。

符号也可以用来描述f在某个实数a（通常为a = 0）附近的行为：我们说

${\ displaystyle f（x）= O（g（x））{\ text {as}} x \ to a}$

当且仅当存在正数δ和M才能使得

${\ displaystyle | f（x）| \ leq \; M | g（x）| {\ text {when}} 0 <| xa | <\ delta}$ 。

如果克（X）是用于值非零X 足够接近到一个，这两种定义的可以使用统一极限优越：

${\ displaystyle f（x）= O（g（x））{\ text {as}} x \ to a}$

如果只有

${\ displaystyle \ limsup _ {x \ to a} \ left | {\ frac {f（x）} {g（x）}} \ right | <\ infty}$ 。

示例[ 编辑]

在典型的使用中，O符号的形式定义不直接使用; 相反，函数f的O符号通过以下简化规则得出：

如果f（x）是几个项的总和，如果有一个具有最大增长率的值，则可以被保留，并且所有其他的省略。
如果f（x）是几个因素的乘积，则可以省略任何常数（不依赖于x的产品中的术语）。

例如，让?F（X）= 6 X ⁴ - 2 X ³ + 5，并假设我们希望简化这种功能，使用?符号，作为描述其增长率X接近无穷大。这个函数是三个项的总和：6 × ⁴，-2 × ³和5.在这三个项中，增长率最高的一个是具有最大指数作为x的函数，即6 × ⁴。现在可以应用第二个规则：6 x ⁴是6和x ⁴的乘积，其中第一个因素不依赖于x。省略这个因素导致x ⁴的简化形式。因此，我们说f（x）是（x ⁴）的“大哦” 。在数学上，我们可以写出f（x）= O（x ⁴）。可以使用正式定义来确认此计算：let f（x）= 6 x ⁴ - 2 x ³ + 5和g（x）= x ⁴。从上面应用正式定义，

${\ displaystyle | f（x）| \ leq \; M | x ^ {4} |}$

对于x ₀和M以及对于所有x > x _0的一些合适的选择。为了证明这一点，让x ₀ = 1和M = 13。然后，对于所有x > x ₀：

${\ displaystyle {\ begin {aligned} | 6x ^ {4} -2x ^ {3} +5 |＆\ leq 6x ^ {4} + | 2x ^ {3} | +5 \\＆\ leq 6x ^ 4} + 2×^ {4} + 5×^ {4} \\＆= 13X ^ {4} \ {端对齐}}}$

所以

$| 6x ^ {4} -2x ^ {3} +5 | \ leq 13 \，x ^ {4}。$

用法[ 编辑]

大O表示法有两个主要的应用领域。在数学中，通常用于描述有限序列近似于给定函数的程度，特别是在截断的泰勒级数或渐近扩展的情况下。在计算机科学中，它在分析算法中是有用的。在这两种应用中，出现在O（...）中的函数g（x）通常被选择为尽可能简单，省略常数因子和较低阶项。这个符号有两个正式接近但明显不同的用法：无限渐近和无穷小渐近。

无限渐近[ 编辑]

在算法分析中通常使用的函数图，显示每个函数的操作次数N与输入大小n

在分析算法的效率时，大O表示法很有用。例如，完成大小为n的问题所需的时间（或步骤数）可能被认为是T（n）= 4 n ² - 2 n + 2。随着n增大，n ² 项将所有其他术语都可以被忽略 - 例如当n = 500时，术语4 n ²是2 n项的1000倍。忽视后者对于大多数用途的表达的价值可能会产生微不足道的影响。进一步，如果我们与任何其他表达顺序进行比较，例如包含术语n ³或n ⁴的表达式，则系数变得无关紧要。即使T（n）= 1,000,000 n ²，如果U（n）= n ³，则如果U（n）= n ³，则后者总是超过前者，一旦n增加大于1,000,000（T（1,000,000）= 1,000,000 ³ = U（1,000,000）））。另外，步数取决于算法运行的机器模型的细节，但是不同类型的机器通常仅仅是执行算法所需的步骤数量的恒定因素。所以大的O表示法捕捉到了什么：我们也写

${\ displaystyle \ T（n）= O（n ^ {2}）}$

要么

$O（n ^ {2}）中的{\ displaystyle T（n）\}$

并且说该算法具有n ²时间复杂度的阶数。请注意，“=”并不意味着在其正常的数学意义上表达“等于”，而是更加口头上的“是”，所以第二个表达有时被认为更准确（参见下面的“ 等价符号 ”），而第一个被认为是滥用符号。^[4]

无穷小渐近[ 编辑]

大O也可以用来描述与数学函数近似的误差项。最重要的术语是明确写出的，然后最小重要术语总结在单个大O术语中。例如，考虑当x小时，指数系列和两个表达式是有效的：

${\ displaystyle {\ begin {aligned} e ^ {x}＆= 1 + x + {\ frac {x ^ {2}} {2！}} + {\ frac {x ^ {3}} {3！}} + {\ frac {x ^ {4}} {4！}} + \ dotsb＆{\ text {for all}} x \\＆= 1 + x + {\ frac {x ^ {2}} {2}} + O（x ^ {3}）＆{\ text {as}} x \ to 0 \\＆= 1 + x + O（x ^ {2}）＆{\ text {as}} x \ \\端{对齐}}}$

第二个表达式（具有?（X ³））指的误差的绝对值? ^X - （1 + X + X ² /2）为至多一些恒定次| x ³ | 当x足够接近0时。

属性[ 编辑]

如果函数f可以写成其他函数的有限和，则最快速生成的函数确定f（n）的顺序。例如，

$f（n）= 9 \ log n + 5（\ log n）^ {3} + 3n ^ {2} + 2n ^ {3} = O（n ^ {3}）\ ,, \ qquad {\ text { as}} n \ to \ infty \，\ !.$

特别地，如果函数可以由n中的多项式限定，则随着n趋于无穷大，可以忽略多项式的低阶项。另外要注意的是集合O（n ^c）和O（c ⁿ）是非常不同的。如果c大于1，则后者增长得更快。对于任何c，生长速度比n ^c快的函数称为超多项式。比形式c ^n的任何指数函数增长得更慢的一个称为子指数。算法可能需要超多项式和子指数的时间; 其示例包括用于整数分解的最快的已知算法和函数n ^logⁿ。

我们可以忽略对数内n的任何权力。集合O（log n）与O（log（n ^c））完全相同。对数不同只是一个常数因子（因为log（n ^c）= c log n），所以大O表示法忽略了这一点。类似地，具有不同常数基数的日志是等效的。另一方面，具有不同基数的指数不一样。例如，²ⁿ和³ⁿ不是相同的顺序。

更改单位可能影响或不影响所得算法的顺序。更改单位相当于将适当的变量乘以常数，无论出现在哪里。例如，如果一个算法在的顺序运行? ²，取代?由CN指的顺序算法运行? ²? ²，而大O符号忽略恒定? ²。这可以写成c ²n ² = O（n ²）。然而，如果算法以2 ⁿ的顺序运行，替换?与CN给出2 ^CN =（2 ^?）^?。这一般不等于2 ⁿ。更改变量也可能会影响生成的算法的顺序。例如，如果一种算法的运行时间是?（?在数目来衡量时）?的位数的输入数的X，则其运行时间为?（日志X时作为输入数的函数测量）X自身，因为n = O（log x）。^{这一般不等于2 n}。更改变量也可能会影响生成的算法的顺序。例如，如果一种算法的运行时间是?（?在数目来衡量时）?的位数的输入数的X，则其运行时间为?（日志X时作为输入数的函数测量）X自身，因为n = O（log x）。^{这一般不等于2 n}。更改变量也可能会影响生成的算法的顺序。例如，如果一种算法的运行时间是?（?在数目来衡量时）?的位数的输入数的X，则其运行时间为?（日志X时作为输入数的函数测量）X自身，因为n = O（log x）。

产品[ 编辑]

${\ displaystyle f_ {1} = O（g_ {1}）{\ text {and}} f_ {2} = O（g_ {2}）\，\ Rightarrow f_ {1} f_ {2} = O {1} G_ {2}）}$
$f \ cdot O（g）= O（fg）$

总和[ 编辑]

${\ displaystyle f_ {1} = O（g_ {1}）{\ text {and}} f_ {2} = O（g_ {2}）\，\ Rightarrow f_ {1} + f_ {2} = O | G_ {1} | + | G_ {2} |）}$

这意味着 $O（g）中的f_ {1} = O（g）{\ text {和}} f_ {2} = O（g）\ Rightarrow f_ {1} + f_ {2}$ ，意思就是 O（克）是一个凸锥。

如果f和g是正函数，

乘以常数[ 编辑]

令k为常数。然后：
$\ O（kg）= O（g）$ 如果k不为零。
$f = O（g）\ Rightarrow kf = O（g）。$

多变量[ 编辑]

大O（和小o和Ω...）也可以与多个变量一起使用。假设要为多个变量正式定义Big O 和是在某些子集上定义的两个函数 $\ mathbb {R} ^ {n}$ 。我们说

$f（{\ vec {x}}）{\ text {is}} O（g（{\ vec {x}}））{\ text {as}} {\ vec {x}} \ to \ infty$

当且仅当^[5]

$\ exists M \，\ exists C> 0 {\ text {such for for all}} {\ vec {x}} {\ text {with}} x_ {i} \ geq M {\ text {for some}} i ，| f（{\ vec {x}}）| \ leq C | g（{\ vec {x}}）|。$

等同的条件 $x_ {i} \ geq M$ 对于一些可以替换为条件 ${\ displaystyle \ | {\ vec {x}} \ | _ {\ infty} \ geq M}$ ，哪里 ${\ displaystyle \ | {\ vec {x}} \ | _ {\ infty}}$ 表示切比雪夫规范。例如，声明

${\ displaystyle f（n，m）= n ^ {2} + m ^ {3} + O（n + m）{\ text {as}} n，m \ to \ infty}$

断言存在常数C和M使得

${\ displaystyle \ forall \ |（n，m）\ | _ {\ infty} \ geq M：| g（n，m）| \ leq C | n + m |，}$

其中g（n，m）由...定义

${\ displaystyle f（n，m）= n ^ {2} + m ^ {3} + g（n，m）}$

请注意，此定义允许所有坐标 ${\ vec {x}}$ 增加到无限远。特别是声明

${\ displaystyle f（n，m）= O（n ^ {m}）{\ text {as}} n，m \ to \ infty}$

（即 $\ exists C \，\ exists M \，\ forall n \，\ forall m \ dots$ ）是完全不同的

$\ forall m \ colon f（n，m）= O（n ^ {m}）{\ text {as}} n \到\ infty$

（即 $\ forall m \，\ exists C \，\ exists M \，\ forall n \ dots$ ）。

这不是大O到多变量函数的唯一泛化，而在实践中，定义的选择存在一些不一致。^[6]

符号事项[ 编辑]

等号[ 编辑]

语句“ ?F（X）是?（克（X））”如上述所定义通常被写成?F（X）= ?（克（X））。有些人认为这是滥用符号，因为使用等号可能会产生误导，因为它表明该声明没有对称性。如de Bruijn所说，O（x）= O（x ²）是真的，但O（x ²）= O（x）不是。^[7] Knuth描述了“单向均衡”这样的语句，因为如果双方可以颠倒，我们可以从身份n = O（n ²）和n ² = O（n ²）中推导出可笑的东西，如n = n ²n ²）“。^[8]

由于这些原因，这将是更精确的使用组符号和写?F（X）∈ ?（克（X）），思维?（克（X）），作为类的所有功能?（X），使得| h（x）| ≤ ? | g（x）| 对于某一常数?。^[8]然而，使用等号是习惯的。Knuth指出，“数学家习惯使用=符号，因为他们使用英语中的”is“：亚里士多德是一个人，但一个人不一定是亚里士多德。

其他算术运算符[ 编辑]

大O符号也可以与其他算术运算符结合使用在更复杂的方程中。例如，h（x）+ O（f（x））表示具有h（x）生长加上其生长受限于f（x）的函数的函数的集合。从而，

${\ displaystyle g（x）= h（x）+ O（f（x））}$

表示相同

$G（X）-H（X）= O（F（X））\ ,.$

例 [ 编辑]

假设正在开发一种对一组n个元素进行操作的算法。它的开发者有兴趣找到一个函数T（n），该函数将表示算法在输入集中的元素数量上运行多长时间（在某些任意的时间测量中）。该算法通过首先调用子例程来对集合中的元素进行排序，然后执行自己的操作。排序具有一个已知的时间复杂度?（? ²），和子程序运行后的算法必须采取额外的55 ? ³ + 2个? 它终止之前+ 10步骤。因此，算法的整体时间复杂度可以表示为T（n）= 55 n ³ + O（n ²）。在这里，术语2 n +10被纳入更快生长的O（n ²）内。再次，这种使用忽略了“=”符号的一些正式含义，但它允许使用大O符号作为一种方便的占位符。

多种用途[ 编辑]

在更复杂的使用中，O（...）可以出现在方程式的不同位置，甚至在每一方都可以出现多次。例如，以下是 $n \到\ infty$

${\ displaystyle（n + 1）^ {2} = n ^ {2} + O（n）}$
${\ displaystyle（n + O（n ^ {1/2}））（n + O（\ log n））^ {2} = n ^ {3} + O（n ^ {5/2}）}$
${\ displaystyle n ^ {O（1）} = O（e ^ {n}）}$

这种说法的含义如下：对于满足左侧每个O（...）的任何函数，存在满足右侧每个O（...）的一些函数，从而将所有这些函数代入该方程使双方平等。例如，上面的第三个方程意味着：对于任何函数f（n）= O（1），存在一些函数g（n）= O（e ⁿ），使得n ^f^（ⁿ^） = g（n）。 “ 就上述“设定符号”而言，意思是由左侧表示的函数类是由右侧表示的函数类的子集。在这种使用中，“=”是一个正式的符号，与通常使用的“=”不同，它不是对称关系。因此，例如，n ^O^（1） = O（e ⁿ）并不意味着虚假陈述O（e ⁿ）= n ^O^（1）

的通用功能的命令[ 编辑]

更多信息：时间复杂度§常见时间复杂度表

以下是分析算法的运行时间时通常遇到的函数类的列表。在每种情况下，c是正常数，n不加限制。增长较慢的功能通常列在第一位。

符号	名称	例
	不变	确定二进制数是偶数还是奇数; 计算 $（-1）^ {N}$ ; 使用常量查询表
$O（\ log \ log n）$	双对数	在均匀分布值排序的数组中使用插值搜索查找项目的比较数
$O（\ log n）$	对数的	使用二进制搜索或平衡搜索树查找排序数组中的项目以及二项式堆中的所有操作
${\ displaystyle O（（\ log n）^ {c}）}$ ${\ displaystyle \ scriptstyle c> 1}$	polylogarithmic	矩阵链排序可以在并行随机存取机器的多对数时间内解决。
$为O（n ^ {C}）$ ${\ displaystyle \ scriptstyle 0 <c <1}$	分数幂	在kd-tree中搜索
	线性	在未排序的列表或未排序的数组中查找项目; 通过波纹携带增加两个n位整数
${\ displaystyle O（n \ log ^ {*} n）}$	? 登录星级 ?	使用塞德尔算法或联合查找算法执行简单多边形的三角测量。注意 $\ log ^ {}（n）= {\ begin {cases} 0，＆{\ text {if}} n \ leq 1 \\ 1+ \ log ^ {}（\ log n），＆ {if}} n> 1 \ end {cases}}$
${\ displaystyle O（n \ log n）= O（\ log n！）}$	线性，线性或准线性	执行快速傅里叶变换 ; 最快的速度比较排序 ; 堆积和合并排序
$为O（n ^ {2}）$	二次	通过简单的算法乘以两个n位数; 简单的排序算法，如气泡排序，选择排序和插入排序 ; （最坏情况）绑定在一些通常更快的排序算法，如快速排序，Shellsort和树排序
$为O（n ^ {C}）$	多项式或代数	树相邻的语法解析; 最大匹配为二分图 ; 用LU分解找到行列式
${\ displaystyle L_ {n} [\ alpha，c] = e ^ {（c + o（1））（\ ln n）^ {\ alpha}（\ ln \ ln n）^ {1- \ alpha}} }$ ${\ displaystyle \ scriptstyle 0 <\ alpha <1}$	L符号或亚指数	使用二次筛或数字筛选分数
${\ displaystyle \ scriptstyle c> 1}$	指数	使用动态规划寻找（精确）解决旅行推销员问题 ; 使用强力搜索确定两个逻辑语句是否相当
	阶乘	通过强力搜索解决旅行推销员问题 ; 产生一个poset的所有无限制排列; 用拉普拉斯扩张找到决定因素 ; 枚举一个集合的所有分区

该声明 ${\ displaystyle f（n）= O（n！）}$ 有时被削弱 $F（N）= O \左（N ^ {N} \右）$ 推导出更简单的渐近复杂度公式。对于任何 K> 0 和 C> 0 ， $O（n ^ {c}（\ log n）^ {k}）$ 是一个子集 $O（n ^ {c + \ varepsilon}）$ 为任何 $\ varepsilon> 0$ ，所以可以被认为是具有更大次序的多项式。

相关渐近记号[ 编辑]

大O是用于比较功能的最常用的渐近符号，尽管在许多情况下，大O可以用大角度θ代替渐近的更紧密的界限。在这里，我们定义一些关于大O的相关符号，进展到大O符号所属的巴赫曼 - 朗道符号家族。

Little-o符号[ 编辑]

“小o”重定向到这里。对于棒球运动员，请参阅Omar Vizquel。

非正式断言“ f（x）是g（x）的小o ”正式写成

${\ displaystyle f（x）= o（g（x））}$ ，

或在集符号?F（X）∈ ?（克（X））。直观地说，这意味着g（x）比 f（x）快得多。

它假设f和g都是一个变量的函数。形式上，?F（?）= ?（克（?））（或?F（?）∈ ?（克（?）））作为? →∞意味着每正的常数ε存在一个常数?使得

${\ displaystyle | f（n）| \ leq \ varepsilon | g（n）| \ qquad {\ text {for all}} n \ geq N?$ ^[8]

请注意早期的大O表示形式定义与小o的定义之间的区别，而前者对于至少一个常数M必须是真实的，后者必须对每个正常数ε保持不变。^[4]这样，小O符号作出强硬的声明比相应的大O表示法：每一个功能并没有多大-O 摹也是大O 摹，但并不是每个功能是大O 克也是小邻克（例如克本身不是，除非它是恒为零∞附近）。

如果g（x）非零，或至少在某一点以上变为非零，则关系f（x）= o（g（x））等于

$\ lim _ {x \ to \ infty} {\ frac {f（x）} {g（x）}} = 0。$

例如，

${\ displaystyle 2x = o（x ^ {2}）}$
$2x ^ {2} \ neq o（x ^ {2}）$

小数字符号在数学中很常见，但在计算机科学中却很少见。在计算机科学中，变量（和函数值）通常是自然数。在数学中，变量和函数值通常是实数。以下属性（以最近的设定理论符号表示）可以是有用的：

对于 $c \ not = 0$
$o（f）o（g）\ subseteq o（fg）$
$o（o（f））\ subseteq o（f）$
$o（f）\子集O（f）$ （因此上述性质适用于o和O的大多数组合）。

与大O符号一样，语句“ f（x）是o（g（x）） ”通常写为f（x）= o（g（x）），这有一些考虑滥用符号。

大欧米茄符号[ 编辑]

声明有两个非常普遍和不相容的定义

$f（x）= \ Omega（g（x））\（x \ rightarrow a），$

其中一个是一些实数，∞，或-∞，其中?F和克在的邻域中定义的真实功能一个，并且其中克是在这附近阳性。

第一个（按时间顺序）用于分析数论，另一个在计算复杂度理论中。当这两个问题相遇时，这种情况势必会产生混乱。

Hardy-Littlewood定义[ 编辑]

在1914年，GH Hardy和JE Littlewood推出了新的标志 $\欧米茄$ ，^[10]定义如下：

$f（x）= \ Omega（g（x））\（x \ rightarrow \ infty）\; \ Leftrightarrow \; \ limsup _ {x \ to \ infty} \ left | {\ frac {f（x）} { G（X）}} \右|> 0$ 。

从而 $f（x）= \Ω（g（x））$ 是否定的 F（X）= O（G（X））。

在1916年，同一作者介绍了两个新的符号 $\ Omega _ {R}$ 和 $\ Omega _ {L}$ ，^[11]因此定义：

$f（x）= \ Omega _ {R}（g（x））\（x \ rightarrow \ infty）\; \ Leftrightarrow \; \ limsup _ {x \ to \ infty} {\ frac {f（x）} {G（X）}}> 0$ ;

$f（x）= \ Omega _ {L}（g（x））\（x \ rightarrow \ infty）\; \ Leftrightarrow \; \ liminf _ {x \ to \ infty} {\ frac {f（x）} {G（X）}} <0$ 。

于是 $f（x）= \ Omega _ {R}（g（x））$ 是否定的 F（X）<O（G（X）），和 $f（x）= \ Omega _ {L}（g（x））$ 是否定的 F（X）> O（G（X））。

与以后的DE Knuth的断言相反，^[12] Edmund Landau在1924年确实使用了这三个符号，含义相同。^[13]

这些Hardy-Littlewood符号是原型，在Landau从未再次使用过之后。

$\ Omega _ {R}$ 成为 $\ Omega _ {+}$ ，和 $\ Omega _ {L}$ 成为 $\ Omega _ { - }$ 。

这三个符号 $\ Omega，\ Omega _ {+}，\ Omega _ { - }$ ，以及 $f（x）= \ Omega _ {\ pm}（g（x））$ （意思是 $f（x）= \ Omega _ {+}（g（x））$ 和 $f（x）= \ Omega _ { - }（g（x））$ 都是满意的），现在被用于分析数论。^[14]

简单的例子[ 编辑]

我们有

$\ sin x = \ Omega（1）\（x \ rightarrow \ infty），$

更确切地说

$\ sin x = \ Omega _ {\ pm}（1）\（x \ rightarrow \ infty）。$

我们有

$\ sin x + 1 = \ Omega（1）\（x \ rightarrow \ infty），$

更确切地说

$\ sin x + 1 = \ Omega _ {+}（1）\（x \ rightarrow \ infty）;$

然而

$\ sin x + 1 \ not = \ Omega _ { - }（1）\（x \ rightarrow \ infty）。$

Knuth定义[ 编辑]

1976年，唐纳德·克努特（Donald Knuth）发表了一篇论文，证明他的使用是正确的 $\欧米茄$ 符号来描述一个更强大的属性。Knuth写道：“对于我迄今为止在计算机科学中看到的所有应用程序，更强的要求[...]更为合适。他定义

$f（x）= \ Omega（g（x））\ Leftrightarrow g（x）= O（f（x））$

评论说：“虽然我已经改变了哈迪和小伍德的定义 $\欧米茄$ 我认为这样做是有道理的，因为他们的定义绝不是广泛使用的，因为还有其他的方式可以在比较罕见的情况下说出他们想要在他们的定义适用时想说的话。“ ^[12]

巴赫曼兰登符号家族[ 编辑]

符号	名称^[12]	描述	正式定义	极限定义^[15]^[16]^[17]^[12]^[10]
	小O; 小哦	被主导渐近	$\ forall k> 0 \; \ exists n_ {0} \; \ forall n> n_ {0} \; \| f（n）\| \ leq k \ cdot \| g（n）\|$	${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {f（n）} {g（n）}} = 0}$
	大O 大哦大Omicron	以上为界（直到恒定因子）渐近	${\ displaystyle \ exists k> 0 \; \ exists n_ {0} \; \ forall n> n_ {0} \; \| f（n）\| \ leq k \ cdot g（n）}$	${\ displaystyle \ limsup _ {n \ to \ infty} {\ frac {\ left \| f（n）\ right \|} {g（n）}} <\ infty}$
$f（n）= \ Theta（g（n））$	大。	在上下都有界限渐近	$\ exists k_ {1}> 0 \; \ exists k_ {2}> 0 \; \ exists n_ {0} \; \ forall n> n_ {0}$ $k_ {1} \ cdot g（n）\ leq f（n）\ leq k_ {2} \ cdot g（n）$	和 $f（n）= \Ω（g（n））$ （Knuth版）
${\ displaystyle f（n）\ sim g（n）}$	按顺序	等于渐近	$\ forall \ varepsilon> 0 \; \存在n_ {0} \; \ forall n> n_ {0} \; \ left \| {f（n）\ over g（n）} - 1 \ right \| <\ varepsilon$	${\ displaystyle \ lim _ {n \ to \ infty} {f（n）\ over g（n）} = 1}$
$f（n）= \Ω（g（n））$	数字理论中的大欧米茄（Hardy-Littlewood）	不是主宰渐近	${\ displaystyle \ exists k> 0 \; \ forall n_ {0} \; \ exists n> n_ {0} \; \| f（n）\| \ geq k \ cdot g（n）}$	${\ displaystyle \ limsup _ {n \ to \ infty} \ left \| {\ frac {f（n）} {g（n）}} \ right \|> 0}$
$f（n）= \Ω（g（n））$	大欧米茄在复杂性理论（Knuth）	在下面是有限的渐近	$\ exists k> 0 \; \ exists n_ {0} \; \ forall n> n_ {0} \; f（n）\ geq k \ cdot g（n）$	${\ displaystyle \ liminf _ {n \ to \ infty} {\ frac {f（n）} {g（n）}}> 0}$
$f（n）= \ omega（g（n））$	小欧米茄	占主导地位渐近	$\ forall k> 0 \; \存在n_ {0} \; \ forall n> n_ {0} \ \| f（n）\| \ geq k \ cdot \| g（n）\|$	${\ displaystyle \ lim _ {n \ to \ infty} \ left \| {\ frac {f（n）} {g（n）}} \ right \| = \ infty}$

极限定义假定 ${\ displaystyle g（n）\ neq 0}$ 足够大。该表从最小到最大排列，在这个意义上，函数的两个版本的Ω，ω对应于实线上的<，≤，≈，=，≥，>。^[17]^：6

计算机科学使用大O，Big ThetaΘ，小o，小omegaω和Knuth的大欧米茄Ω符号。^[18]分析数学理论通常使用大O，小o，Hardy-Littlewood的大OmegaΩ和 $\ SIM卡$ 符号。^[14]小欧米茄ω符号在分析中不常用。^[19]

使用计算机科学[ 编辑]

有关此主题的更多详细信息，请参阅算法分析。

非正式地，特别是在计算机科学中，大O符号通常被允许在某种情况下被用来形容一个渐近的紧边，其中使用Big ThetaΘ表示法在事实上更恰当。^{[ 引证需要 ]}例如，考虑功能时?（?）= 73 ? ³ + 22 ? ² + 58，以下所有的通常都是可接受的，但更严格的界限（即，数字2和表3）通常是强烈优选的越过越界（即下面的1号）。

T（n）= O（n ¹⁰⁰）
T（n）= O（n ³）
T（n）=Θ（n ³）

相应的英文语句分别为：

T（n）渐近渐近不比n ¹⁰⁰快
T（n）渐近渐近不比n ³快
T（n）渐近地与n ^3一样长。

所以三个陈述都是真实的，每个都包含更多的信息。然而，在某些领域中，大O表示法（上述列表中的第2列）将比“大号”（Big Theta）符号（上面列表中的子弹号3）更为常用。例如，如果T（n）表示新开发的输入大小为n的算法的运行时间，则算法的发明人和用户可能更倾向于在不做任何操作的情况下运行需要多长时间的上渐近界限关于较低渐近界限的明确声明。

其他符号[ 编辑]

在他们的著作算法导论，Cormen，Leiserson，维斯特和斯坦考虑的功能集摹到其中的一些功能?F属于当满足

${\ displaystyle f（n）= O（g（n））\（n \ rightarrow \ infty）}$

以正确的符号表示，这个集合可以被称为O（g），其中

${\ displaystyle O（g）= \ {f：}$ 存在正常常数c和 $N_ {0}$ 就这样 ${\ displaystyle 0 \ leq f（n）\ leq cg（n）}$ 对全部 ${\ displaystyle n \ geq n_ {0} \}}$ 。^[20]

作者声明，使用等号运算符（=）来表示集合成员资格而不是集合隶属运算符（∈）是滥用符号，但这样做具有优势。^[21]等式或不等式内部，使用渐近符号的代表组中的一个匿名函数?（克），这消除了较低阶项，并且有助于减少在方程无关紧要杂波，例如：^[22]

${\ displaystyle 2n ^ {2} + 3n + 1 = 2n ^ {2} + O（n）}$

扩展到巴赫曼-兰道记号[ 编辑]

f（n）= ?（g（n））是f（n）= O（g（n）log ^k g（n））的缩写，用于计算机科学中有时使用的另一个符号是（读取软O）一些?。基本上，它是大的O表示法，忽略对数因素，因为一些其他超对数函数的增长率效应表明对于大型输入参数的增长率爆炸，对于预测运行时性能较差而言更为重要由对数生长因子贡献的点效应。

也是L表示法，定义为

${\ displaystyle L_ {n} [\ alpha，c] = e ^ {（c + o（1））（\ ln n）^ {\ alpha}（\ ln \ ln n）^ {1- \ alpha}} }$

对于在多项式和指数之间的函数是方便的 $\ ln n$ 。

推广和相关用法[ 编辑]

在任何规范向量空间中获取值的函数的泛化是简单的（将绝对值替换为规范），其中f和g不需要在相同空间中取值。泛化到功能克在任何取值拓扑群也是可能^{[ 引证需要 ]}。“限制过程” x→x _o也可以通过引入任意的过滤器基，即定向网 f和g来推广。

$f（\ g）iff（fg）\ in o（g）$

这是与上述关系“ f为Θ（g）” 的等价关系和更为限制性的概念。（如果f和g是正实值函数，则它减少到lim f / g = 1 ）例如，2 x是Θ（x），但是2 x - x不是o（x）。

历史（Bachmann-Landau，Hardy和Vinogradov符号）[ 编辑]

符号○最早是由数量理论家引进保罗巴赫曼于1894年，在他的书的第二卷Analytische Zahlentheorie（“ 解析数论 ”），其中第一册（尚未包含大O表示法）发表于1892年^{[ 1]}数理论家埃德蒙·兰多（Edmund Landau）采用它，因此被启发于1909年引入符号o; ^[2]因此两者现在都称为Landau符号。这些符号被用于20世纪50年代的应用数学中，用于渐近分析。^[23]符号 $\欧米茄$ （在这个意义上“不是?的”）由Hardy和的Littlewood于1914年被引入。^[10]哈代和小伍德也在1918年引入了符号 $\ Omega _ {R}$ （“正确”）和 $\ Omega _ {L}$ （“左”），^[11]现代符号的前身 $\ Omega _ {+}$ （“不小于小”）和 $\ Omega _ { - }$ （“不大于小”）。因此，欧米茄符号（具有其原始含义）有时也被称为“Landau符号”。这个符号 $\欧米茄$ 至少在20世纪50年代以来，数字理论成为常用的数学理论。^[20] 20世纪70年代，大O在计算机科学中普及，唐纳德·克努特（Donald Knuth）推出了相关的Theta符号，并提出了一个不同的欧米茄符号定义。^[12]

兰多从来没有使用过大的Theta和小欧米茄符号。

哈代的符号是（在现代O符号方面）

${\ displaystyle f \ preccurlyeq g \ iff f \ in O（g）}$ 和 $o（g）中的f \ prec g \ iff f \$

（Hardy从来没有定义或使用符号 $\ prec \！\！\ prec$ ，也不 $\二$ ，因为它有时被报告）。还应该指出，哈代介绍了这些符号 $\ preccurlyeq$ 和 $\ PREC$ （以及一些其他符号）在他的1910年的“无限命令”中，仅在三篇论文（1910-1913）中使用。在他近400余篇论文和书籍中，他一直使用Landau符号O和o。

哈代的符号不再被使用了。另一方面，在20世纪30年代，^[25]俄罗斯数理论家伊万·马特维耶维奇·维诺格拉夫夫介绍了他的记法 $\二$ ，这在数理论中已经越来越多地被使用了符号。我们有