[DS] 2017-04-03_Asymptotic Notations

表示時間函數的成長速率等級

＃Big-oh: O

Def: f( n ) = O( g( n ) ) iff for all constant C > 0, 存在n0 > 0, 

        such that 0 ≦ f( n ) ≦ C*g( n ) for all n ≧ n0

＃Big-omega: Ω

Def: f( n ) = Ω( g( n ) ) iff for all constant C > 0, 存在n0 > 0, 

        such that 0 ≦ C*g( n ) ≦ f( n )  for all n ≧ n0

＃Theta: θ

Def: f( n ) = θ( g( n ) ) iff for all constant C1, C2 > 0, 存在n0 > 0, 

        such that C1*g( n ) ≦ f( n ) ≦ C2*g( n ) for all n ≧ n0

＃Little-oh: o

Def: f( n ) = o( g( n ) ) iff for all constant C > 0, 存在n0 > 0,
        such that 0 ≦ f( n ) < C*g( n ) for all n ≧ n0

＃Little-omega: ω

Def: f( n ) = ω( g( n ) ) iff for all constant C > 0, 存在n0 > 0,
        such that 0 ≦ C*g( n ) < f( n ) for all n ≧ n0