大O记号的引入和其他记号

大O记号是为了找出某个算法随问题输入规模n的增大时 

算法的时间成本随着n的变化

我们知道当n变得很大时  我们只需要关心最高次的n就好了

渐进分析 大O记号

大O记号 

T(n)=O(f(n))      c大于0  n远大于2的话  T(n)<c*f(n) 

对于一个算法要以长远的、主流的眼光来看待

所谓长远就是n趋于无穷大 至少远远大于2

主流就是  只看最高次数项 忽略旁枝末节的地方

可将大O曲线看作T(n)的上界或者说 最坏情况

n较小时 大O曲线未必是一定小于T(n)的  但是到了后面n大了以后一定是曲线O大于T(n)

事实上我们说  对于一个适当选取的约定好的常数c 是一定有曲线O大于T(n)的、

即c放大后能起到上界的作用

大欧米伽是最好的情况 是下界

思特是代表了确界

一般考虑的是最坏情况 也就是O的情况