大O符号(英語:Big O notation),又稱為漸進符號,是用于描述函数渐近行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。
大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》(Analytische Zahlentheorie)首先引入的。而这个记号则是在另一位德国数论学家愛德蒙·蘭道的著作中才推广的,因此它有时又称为蘭道符号(Landau symbols)。代表“order of ...”(……阶)的大O,最初是一个大写希腊字母“Ο”(omicron),现今用的是大写拉丁字母“O”。
Knuth, Donald. 1.2.11: Asymptotic Representations. Fundamental Algorithms. The Art of Computer Programming 1 3rd. Addison–Wesley. 1997. ISBN 0-201-89683-4.
Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing. 1997: 226–228. ISBN 0-534-94728-X.
Avigad, Jeremy; Donnelly, Kevin. Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. 2004. doi:10.1007/978-3-540-25984-8_27.
Black, Paul E. Black, Paul E. , 编. big-O notation. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 11 March 2005 [December 16, 2006]. (原始内容于2019-05-20).
Black, Paul E. Black, Paul E. , 编. little-o notation. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. (原始内容于2020-11-01).
Black, Paul E. Black, Paul E. , 编. Ω. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. (原始内容于2021-01-25).
Black, Paul E. Black, Paul E. , 编. ω. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. (原始内容于2021-01-26).
Black, Paul E. Black, Paul E. , 编. Θ. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. (原始内容于2021-01-26).
十月 21, 2023
大o符号, 英語, notation, 又稱為漸進符號, 是用于描述函数渐近行为的数学符号, 更确切地说, 它是用另一个, 通常更简单的, 函数来描述一个函数数量级的渐近上界, 在数学中, 它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项, 在计算机科学中, 它在分析算法复杂性的方面非常有用, 是由德国数论学家保罗, 巴赫曼在其1892年的著作, 解析数论, analytische, zahlentheorie, 首先引入的, 而这个记号则是在另一位德国数论学家愛德蒙, 蘭道的著作中才推广的, 因此它有时又称为. 大O符号 英語 Big O notation 又稱為漸進符號 是用于描述函数渐近行为的数学符号 更确切地说 它是用另一个 通常更简单的 函数来描述一个函数数量级的渐近上界 在数学中 它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项 在计算机科学中 它在分析算法复杂性的方面非常有用 大O符号是由德国数论学家保罗 巴赫曼在其1892年的著作 解析数论 Analytische Zahlentheorie 首先引入的 而这个记号则是在另一位德国数论学家愛德蒙 蘭道的著作中才推广的 因此它有时又称为蘭道符号 Landau symbols 代表 order of 阶 的大O 最初是一个大写希腊字母 O omicron 现今用的是大写拉丁字母 O 目录 1 使用 1 1 无穷大渐近 1 2 无穷小渐近 2 形式化定义 3 例子 4 常用的函数阶 5 一些相关的渐近符号 6 注意 7 参看 8 参考文献 8 1 引用 8 2 来源 9 延伸閱讀使用 编辑无穷大渐近 编辑 大O符号在分析算法效率的时候非常有用 举个例子 解决一个规模为n displaystyle n nbsp 的问题所花费的时间 或者所需步骤的数目 可以表示為 T n 4 n 2 2 n 2 displaystyle T n 4n 2 2n 2 nbsp 当n displaystyle n nbsp 增大时 n 2 displaystyle n 2 nbsp 项将开始占主导地位 而其他各项可以被忽略 举例说明 当n 500 displaystyle n 500 nbsp 4 n 2 displaystyle 4n 2 nbsp 项是2 n displaystyle 2n nbsp 项的1000倍大 因此在大多数场合下 省略后者对表达式的值的影响将是可以忽略不计的 进一步看 如果我们与任一其他级的表达式比较 n 2 displaystyle n 2 nbsp 项的系数也是无关紧要的 例如 一个包含n 3 displaystyle n 3 nbsp 或n 2 displaystyle n 2 nbsp 项的表达式 即使T n 1 000 000 n 2 displaystyle T n 1 000 000 cdot n 2 nbsp 假定U n n 3 displaystyle U n n 3 nbsp 一旦n displaystyle n nbsp 增长到大于1 000 000 后者就会一直超越前者 T 1 000 000 1 000 000 3 U 1 000 000 displaystyle T 1 000 000 1 000 000 3 U 1 000 000 nbsp 这样 針對第一個例子T n 4 n 2 2 n 2 displaystyle T n 4n 2 2n 2 nbsp 大O符号就记下剩余的部分 写作 T n O n 2 displaystyle T n in mathrm O n 2 nbsp 或 T n O n 2 displaystyle T n mathrm O n 2 nbsp 并且我们就说该算法具有n 2 displaystyle n 2 nbsp 阶 平方阶 的时间复杂度 无穷小渐近 编辑 大O也可以用来描述数学函数估计中的误差项 例如e x displaystyle e x nbsp 的泰勒展开 e x 1 x x 2 2 O x 3 displaystyle e x 1 x frac x 2 2 hbox O x 3 qquad nbsp 当x 0 displaystyle x to 0 nbsp 时这表示 如果x displaystyle x nbsp 足够接近于0 那么误差e x 1 x x 2 2 displaystyle e x left 1 x frac x 2 2 right nbsp 的绝对值小于x 3 displaystyle x 3 nbsp 的某一常数倍 注 泰勒展开的误差余项r 3 x displaystyle r 3 x nbsp 是关于x 3 displaystyle x 3 nbsp 一个高阶无穷小量 用小o来表示 即 r 3 x displaystyle r 3 x nbsp o x 3 displaystyle o x 3 nbsp 也就是lim x 0 r 3 x x 3 0 displaystyle lim x to 0 frac r 3 x x 3 0 nbsp 形式化定义 编辑給定兩個定義在實數某子集上的關於x displaystyle x nbsp 的函數f x displaystyle f x nbsp 和g x displaystyle g x nbsp 當x displaystyle x nbsp 趨近於無窮大時 存在正实數M displaystyle M nbsp 使得對於所有充分大 英语 sufficiently large 的x displaystyle x nbsp 都有f x displaystyle f x nbsp 的絕對值小於等於M displaystyle M nbsp 乘以g x displaystyle g x nbsp 的絕對值 那麼我們就可以說 當x displaystyle x to infty nbsp 時 f x O g x displaystyle f x mathrm O g x nbsp 也就是說 假如存在正實數M displaystyle M nbsp 和實數x displaystyle x nbsp 0 使得對於所有的x x 0 displaystyle x geq x 0 nbsp 均有 f x M g x displaystyle f x leq M g x nbsp 成立 我們就可以認爲 f x O g x displaystyle f x mathrm O g x nbsp 在很多情況下 我們會省略 當x displaystyle x nbsp 趨近於無限大時 這個前提 而簡寫爲 f x O g x displaystyle f x mathrm O g x nbsp 此概念也可以用於描述函數f displaystyle f nbsp 在接近實數a displaystyle a nbsp 時的行爲 通常a 0 displaystyle a 0 nbsp 當我們說 當x a displaystyle x to a nbsp 時 有f x O g x displaystyle f x mathrm O g x nbsp 也就相當於稱 當且僅當存在正實數M displaystyle M nbsp 和實數d displaystyle delta nbsp 使得對於所有的0 x a d displaystyle 0 leq x a leq delta nbsp 均有 f x M g x displaystyle f x leq M g x nbsp 成立 如果當x displaystyle x nbsp 和a displaystyle a nbsp 足夠接近時 g x displaystyle g x nbsp 的值仍不爲0 這兩種定義就可以統一用上極限來表示 當且僅當lim sup x a f x g x lt displaystyle limsup x to a left frac f x g x right lt infty nbsp 時 有f x O g x displaystyle f x mathrm O g x nbsp 例子 编辑在具体的运用中 我们不一定使用大O符号的标准定义 而是使用几条简化规则来求出关于函数f displaystyle f nbsp 的大O表示 假如f x displaystyle f x nbsp 是几项之和 那么只保留增长最快 通常是阶最高 的项 其他项省略 假如f x displaystyle f x nbsp 是几项之积 那么常数 不取决于x的乘数 省略 比如 使f x 6 x 4 2 x 3 5 displaystyle f x 6x 4 2x 3 5 nbsp 我们想要用大O符号来简化这个函数 来描述x displaystyle x nbsp 接近无穷大时函数的增长情况 此函数由三项相加而成 6 x 4 displaystyle 6x 4 nbsp 2 x 3 displaystyle 2x 3 nbsp 和5 displaystyle 5 nbsp 由于增长最快的是6 x 4 displaystyle 6x 4 nbsp 这一项 因为阶最高 在x接近无穷大时 其对和的影响会大大超过其余两项 应用第一条规则 保留它而省略其他两项 对于6 x 4 displaystyle 6x 4 nbsp 由两项相乘而得 6 displaystyle 6 nbsp 和x 4 displaystyle x 4 nbsp 应用第二条规则 6 displaystyle 6 nbsp 是无关x的常数 所以省略 最后结果为x 4 displaystyle x 4 nbsp 也即g x x 4 displaystyle g x x 4 nbsp 故有 由f x O g x displaystyle f x mathrm O g x nbsp 可得 6 x 4 2 x 3 5 O x 4 displaystyle 6x 4 2x 3 5 O x 4 nbsp 我们可以将上式扩展为标准定义形式 对任意x x 0 displaystyle x geq x 0 nbsp 均有 f x M g x displaystyle f x leq M g x nbsp 也就是6 x 4 2 x 3 5 M x 4 displaystyle 6x 4 2x 3 5 leq M x 4 nbsp 可以 粗略 求出M displaystyle M nbsp 和x 0 displaystyle x 0 nbsp 的值来验证 使x 0 1 displaystyle x 0 1 nbsp 6 x 4 2 x 3 5 6 x 4 2 x 3 5 6 x 4 2 x 4 5 x 4 13 x 4 displaystyle begin aligned 6x 4 2x 3 5 amp leq 6x 4 2x 3 5 amp leq 6x 4 2x 4 5x 4 amp leq 13x 4 end aligned nbsp 故M displaystyle M nbsp 可以为13 故两者都存在 常用的函数阶 编辑下面是在分析算法的时候常见的函数分类列表 所有这些函数都处于n displaystyle n nbsp 趋近于无穷大的情况下 增长得慢的函数列在上面 c displaystyle c nbsp 是一个任意常数 符号 名称O 1 displaystyle mathrm O 1 nbsp 常数 阶 下同 O log n displaystyle mathrm O log n nbsp 对数O log n c displaystyle mathrm O log n c nbsp 多对数O n displaystyle mathrm O n nbsp 线性 次线性O n log n displaystyle mathrm O n log n nbsp log n displaystyle log n nbsp 為迭代对数O n log n displaystyle mathrm O n log n nbsp 线性对数 或对数线性 拟线性 超线性O n 2 displaystyle mathrm O n 2 nbsp 平方O n c Integer c gt 1 displaystyle mathrm O n c operatorname Integer c gt 1 nbsp 多项式 有时叫作 代数 阶 O c n displaystyle mathrm O c n nbsp 指數 有时叫作 几何 阶 O n displaystyle mathrm O n nbsp 阶乘 有时叫做 组合 阶 一些相关的渐近符号 编辑大O是最经常使用的比较函数的渐近符号 符号 定义f n O g n displaystyle f n mathrm O g n nbsp 渐近上限f n o g n displaystyle f n o g n nbsp Asymptotically negligible渐近可忽略不计 lim f n g n 0 displaystyle lim frac f n g n 0 nbsp f n W g n displaystyle f n Omega g n nbsp 渐近下限 当且仅当g n O f n displaystyle g n mathrm O f n nbsp f n w g n displaystyle f n omega g n nbsp Asymptotically dominant渐近主导 当且仅当g n o f n displaystyle g n o f n nbsp f n 8 g n displaystyle f n Theta g n nbsp Asymptotically tight bound渐近紧约束 当且仅当f n O g n displaystyle f n mathrm O g n nbsp 且f n W g n displaystyle f n Omega g n nbsp 注意 编辑大O符号经常被误用 有的作者可能会使用大O符号表达大8符号的含义 因此在看到大O符号时应首先确定其是否为误用 参看 编辑O 拉丁字母 小o符號 大W符号 大8符号参考文献 编辑引用 编辑 来源 编辑 书籍严蔚敏 吴伟民 数据结构 C语言版 清华大学出版社 1996 ISBN 7 302 02368 9 1 4节 算法和算法分析 pp 14 17 朱青 計算機算法與程序設計 清华大学出版社 2009 10 ISBN 978 7 302 20267 7 1 4节 算法的複雜性分析 pp 16 17 延伸閱讀 编辑Hardy G H Orders of Infinity The Infinitarcalcul of Paul du Bois Reymond Cambridge University Press 1910 Knuth Donald 1 2 11 Asymptotic Representations Fundamental Algorithms The Art of Computer Programming 1 3rd Addison Wesley 1997 ISBN 0 201 89683 4 Cormen Thomas H Leiserson Charles E Rivest Ronald L Stein Clifford 3 1 Asymptotic notation Introduction to Algorithms 2nd MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Sipser Michael Introduction to the Theory of Computation PWS Publishing 1997 226 228 ISBN 0 534 94728 X Avigad Jeremy Donnelly Kevin Formalizing O notation in Isabelle HOL PDF International Joint Conference on Automated Reasoning 2004 doi 10 1007 978 3 540 25984 8 27 Black Paul E Black Paul E 编 big O notation Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology 11 March 2005 December 16 2006 原始内容存档于2019 05 20 Black Paul E Black Paul E 编 little o notation Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology 17 December 2004 December 16 2006 原始内容存档于2020 11 01 Black Paul E Black Paul E 编 W Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology 17 December 2004 December 16 2006 原始内容存档于2021 01 25 Black Paul E Black Paul E 编 w Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology 17 December 2004 December 16 2006 原始内容存档于2021 01 26 Black Paul E Black Paul E 编 8 Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology 17 December 2004 December 16 2006 原始内容存档于2021 01 26 取自 https zh wikipedia org w index php title 大O符号 amp oldid 76518563 一些相关的渐近符号, 维基百科,wiki,书籍,书籍,图书馆,