算法分析基础符号

定义1    [大写O符号] f (n) = O ( g(n) ) 当且仅当存在正的常数c 和n0，使得对于所有的n≥n0 , 有f (n) ≤c g(n)。

定义2    [Ω符号] f (n) = Ω ( g(n) ) 当且仅当存在正的常数c 和n0，使得对于所有的n≥n0, 有f (n) ≥cg (n)。

定义3    [Θ符号] f (n) = Θ( g(n) )当且仅当存在正常数c1 , c2 和某个n0，使得对于所有的n≥n0 , 有c1 g(n)≤f (n)≤c2 g (n)。

定义4    [小写o符号] f (n) = o( g(n) )当且仅当f (n) = O (g (n) )且f (n)≠W (g (n) )。

 

这几个符号都是算法分析最基本的符号，看概念有时候会让人混淆，我是这样记得：

f (n) = O (g (n))代表g(n)是f(n)的一个上界，即f(n)的增长率小于等于(≤)g(n)的增长率，如n^2 = O(n^3)，若f(n) = n^2, g(n) = 2n^2, 从而f(n) = O(g(n))也是正确的；

f (n) =Ω (g (n)) 代表g(n)是f(n)的一个下界，和O符号的意义正好相反，代表f(n)的增长率大于等于(≥)g(n)的增长率；

f (n) = Θ(g (n)) 代表两个函数以相同的速率增长，若f(n) = 2n^2，则写成f(n) = Θ(n^2)是最好的答案；

f (n) = o (g (n)) 和大O符号的意义基本相同，除了相等的情况外，即表示f(n)的增长率小于(<)g(n)的增长率.