|
|
问题:无穷小比较时的';o';是什么单词的首字符?
大 O 符号
---------
大 O 符号(Big O notation)是用于描述函数渐近行为的数学符号。
更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。
在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科
学中,它在分析算法复杂性的方面非常有用。
大 O 符号是由德国数论学家保罗·巴赫曼(Paul Bachmann)在其1892年的著作
《解析数论》(Analytische Zahlentheorie)首先引入的。而这个记号则是在
另一位德国数论学家艾德蒙·朗道(Edmund Landau)的著作中才推广的,因此
它有时又称为朗道符号(Landau symbols)。代表“order of ...”(……阶)
的大 O,最初是一个大写的希腊字母希腊字母';Ο';(Omicron),现今用的是大写
拉丁字母‘O’,但从来不是阿拉伯数字 ‘0’。
形式化定义
----------
给定两正值函数 f 和 g , 定义: f(n)=O(g(n)) , 条件为: 存在正数 c 和 N ,
使得对于所有的 n≥N , 有 f(n)≤cg(n) 。
上述的定义表明,当 n 足够大,大过一个特定的 N 时,且存在一个正数 c ,
使得 f 不大于 cg(n) , 则 f 是 g 的 O 表示。f 和 g 的关系可以理解为 g(n)
是 f(n) 的一个上界,也可以理解为 f 最终至多增涨的速度与 g 一样快,但不会
超过 g 的增涨速度。
|
|