大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符号正好相反,表示总大于。即:
大Θ符号是大O符号和大Ω符号的结合。即:
若
References: