数据结构：渐进记法详解
数据结构：渐进记法详解
渐进记法有三种表示：
1.大O记法：T(n)=O(f(n))表示存在常数c>0,n0>0,使得当n>=n0时，有T(n)<=cf(n)。
2.Ω记法：T(n)=Ω(f(n))表示存在常数c>0,n0>0,使得当n>=n0时，有T(n)>=cf(n)。
3.Q记法：Q(f(n))表示同时有T(n)=O(f(n))和T(n)=Ω(f(n))。
说明：
对于法大O记法，在n为无穷大时，f(n)是T(n)的某种上界（一般指最小上界），而Ω记法是指f(n)是T(n)的某种下界（一般指最大下界），而Q记法则是指两者同时成立，等价。
分析窍门
1.若T(n)是关于n的k阶多项式，T(n)=Q(nk)。
2.for循环时间复杂度等于循环次数乘以循环体代码复杂度
3.对于if-else循环，复杂度判断包括if语句的条件判断，if代码块和else代码块，取最大的作为复杂度
关于复杂度的一些图表
当输入规模相同时，不同的复杂度需要的步数
对于不同的n，不同时间复杂度运行的时间对比
采用曲线的方式对比，更为直观