漸進(jìn)符號(hào)
1瓷马、Θ記號(hào) Θ(g(n)) = { f(n) : 若存在正常數(shù)c1,c2和n0,使對(duì)所有n>=n0時(shí)有0<=c1g(n)<=f(n)<=c2g(n)}
其效果相當(dāng)于刪除f(n)中的低階項(xiàng)纠永，并忽略最高階項(xiàng)的系數(shù)橱乱。
2竹捉、Ο記號(hào) Ο(g(n)) = { f(n) : 存在正常數(shù)c和n0,使對(duì)所有n>=n0,有0<=f(n)<=c*g(n) }
Ο記號(hào)在一個(gè)常數(shù)因子內(nèi)給出某函數(shù)的一個(gè)上界。f(n) = Ο(g(n))表示f(n)是集合O(g(n))的一個(gè)元素廊镜。f(n) = Θ(g(n))隱含著f(n) = Ο(g(n)),因?yàn)棣ㄓ浱?hào)強(qiáng)于Ο記號(hào)榜聂。對(duì)f(n) = Ο(g(n))只能說明g(n)的某個(gè)常數(shù)倍是f(n)的漸近上界，而不反映該上界如何接近陌凳。Ο記號(hào)在用作對(duì)算法最壞情況運(yùn)行時(shí)間的上界時(shí)就有對(duì)任意輸入的運(yùn)行時(shí)間的上界剥懒。
3、Ω記號(hào) Ω(g(n)) = { f(n) : 存在正常數(shù)c和n0,使所有n>=n0有0<=c*g(n)<=f(n) }
Ω記號(hào)給出一個(gè)函數(shù)的漸近下界合敦。
對(duì)于上面三種初橘，有下面的定理：
對(duì)任意兩個(gè)函數(shù)f(n)和g(n),f(n) = Θ(g(n))當(dāng)且僅當(dāng)f(n) = Ο(g(n))和f(n) = Ω(g(n)).
4、其它符號(hào)
ο記號(hào)：Ο記號(hào)提供的漸近上界可能是也可能不是漸近緊確的充岛。2n^2 = Ο(n^2)是漸近緊確的壁却，而2n = O(n^2)不是。而o記號(hào)用來表示非漸近緊確的裸准。 o(g(n)) = { f(n) : 對(duì)任意正常數(shù)c展东，存在正常數(shù)n0,使對(duì)所有n>=n0,有0<=f(n)<=c*g(n) }
ω記號(hào)：ω記號(hào)與Ω記號(hào)的關(guān)系和o記號(hào)與Ο記號(hào)的關(guān)系一樣，不在多說炒俱。
總之盐肃，可以這樣理解，Θ記號(hào)相當(dāng)于"=",Ο相當(dāng)于“<=",Ω相當(dāng)于”>=",o相當(dāng)于“<",ω相當(dāng)于">".這樣理解只用于區(qū)別不同漸近記號(hào)間的關(guān)系权悟，其實(shí)每個(gè)漸近記號(hào)為一個(gè)函數(shù)集合砸王，而非兩個(gè)數(shù)關(guān)系那樣的。
________________________________________-
對(duì)于任何數(shù)學(xué)函數(shù)峦阁，這三個(gè)記號(hào)可以用來度量其“漸近表現(xiàn)”谦铃，即當(dāng)趨于無窮大時(shí)的階的情況，這是算法分析中非常重要的概念榔昔。大家可以把它們分別想象成≤驹闰、≥和 =，分別估計(jì)了函數(shù)的漸近上界撒会、漸近下界和準(zhǔn)確界嘹朗。誠然，漸近關(guān)系和確切大小關(guān)系是有區(qū)別的诵肛，但當(dāng)問題規(guī)模很大時(shí)屹培，忽略這種區(qū)別能大大降低算法分析的難度。
設(shè)函數(shù)f ( n )代表某一算法在輸入大小為n的情況下的工作量（效率），則在n趨向很大的時(shí)候褪秀，我們將f (n)與另一行為已知的函數(shù)g(n)進(jìn)行比較：
1）如果=0蓄诽，則稱f (n)在數(shù)量級(jí)上嚴(yán)格小于g(n)，記為f (n)=o( g(n))媒吗。
2）如果無窮若专，則稱f (n)在數(shù)量級(jí)上嚴(yán)格大于g(n)，記為f (n)=ω ( g(n))蝴猪。
3）如果=c，這里c為非0常數(shù)膊爪，則稱f (n)在數(shù)量級(jí)上等于g(n)自阱，即f (n)和g(n)是同一個(gè)數(shù)量級(jí)的函數(shù)，記為：f (n)=Θ( g(n))米酬。
4）如果f (n)在數(shù)量級(jí)上小于或等于g(n)沛豌，則記為f (n)=O( g(n))。
5）如果f(n)在數(shù)量級(jí)上大于或等于g(n)赃额，則記為f (n)=Ω( g(n))加派。
這里我們假定f (n)，g (n)是非負(fù)單調(diào)的跳芳，且極限存在芍锦。如果這個(gè)極限不存在，則無法對(duì)f (n)和g (n)進(jìn)行比較飞盆。在進(jìn)行此種計(jì)算時(shí)娄琉，一個(gè)經(jīng)常用到的技術(shù)是洛必達(dá)（L'Hopital）法則。該法則由17世紀(jì)法國數(shù)學(xué)家Guillaume de L'Hopital發(fā)現(xiàn)（也有人認(rèn)為是瑞士數(shù)學(xué)家Johann Bernoulli發(fā)現(xiàn)的）吓歇。該法則聲稱孽水，兩個(gè)函數(shù)的比率極限等于兩個(gè)函數(shù)的導(dǎo)數(shù)的比率極限，這里當(dāng)然假定兩個(gè)函數(shù)的導(dǎo)數(shù)比率的極限存在城看，即有：
有了這個(gè)定義女气，就可以對(duì)素性測試的兩個(gè)算法進(jìn)行比較了。
符合第1個(gè)定義测柠，因此這兩個(gè)素性測試算法的效率差異是數(shù)量級(jí)的差異炼鞠。
在算法分析中，最常選取的g(n)有如下一些：
參考文章
http://blog.csdn.net/shadow132/article/details/50546834
求和的基本公式
對(duì)無窮幾何級(jí)數(shù)求導(dǎo)再同乘以x可得：
再求導(dǎo)轰胁，乘x：
