大O符号基础
2018-10-19 本文已影响1人
㭍葉
大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:
