大O表示法

如果算法A需要的时间与f(n)成正比，则算法A成为f(n)阶，表示为O(f(n))。函数f(n)称为算法的增率函数（growth-rate function）。该表示法使用大写字母O来表示（order），故称大O表示法。若规模为n的问题需要的时间与n成正比，则问题表示为O(n),即n阶。若需要的时间与n^2成正比，则问题表示为O(n^2)，以此类推。
下面是算法的阶的定义。
若存在常量k和n0,使算法A在解决规模n>=n0的问题时，需要的问题单元不大于k*f(n),则算法A为f(n)阶，表示为O(f(n))。
O(f(n))定义中的条件n>=n0正式阐明了问题规模足够大的概念，一般地，有很多k和n值可以满足这个定义。大O表示法的几个数学属性有助于简化算法分析。在讨论这些属性是要记住，O(f(n))意为f(n)阶，O并不是一个函数。
1）可忽略算法增率函数的低阶项。
2）可忽略算法增率函数中高阶项的倍数常量。
3）O(f(n))+O(g(n))=O(f(n)+g(n))可组合增率函数。