不卡日日骚,日韩情色中文,粉嫩视频五区在线

漸進符號

1、Θ記號 Θ(g(n)) = { f(n) : 若存在正常數(shù)c1,c2和n0,使對所有n>=n0時有0<=c1g(n)<=f(n)<=c2g(n)}

其效果相當(dāng)于刪除f(n)中的低階項，并忽略最高階項的系數(shù)。

2、Ο記號 Ο(g(n)) = { f(n) : 存在正常數(shù)c和n0,使對所有n>=n0,有0<=f(n)<=c*g(n) }

Ο記號在一個常數(shù)因子內(nèi)給出某函數(shù)的一個上界。f(n) = Ο(g(n))表示f(n)是集合O(g(n))的一個元素。f(n) = Θ(g(n))隱含著f(n) = Ο(g(n)),因為Θ記號強于Ο記號。對f(n) = Ο(g(n))只能說明g(n)的某個常數(shù)倍是f(n)的漸近上界，而不反映該上界如何接近。Ο記號在用作對算法最壞情況運行時間的上界時就有對任意輸入的運行時間的上界。

3、Ω記號 Ω(g(n)) = { f(n) : 存在正常數(shù)c和n0,使所有n>=n0有0<=c*g(n)<=f(n) }

Ω記號給出一個函數(shù)的漸近下界。

對于上面三種，有下面的定理：

對任意兩個函數(shù)f(n)和g(n),f(n) = Θ(g(n))當(dāng)且僅當(dāng)f(n) = Ο(g(n))和f(n) = Ω(g(n)).

4、其它符號

ο記號：Ο記號提供的漸近上界可能是也可能不是漸近緊確的。2n^2 = Ο(n^2)是漸近緊確的，而2n = O(n^2)不是。而o記號用來表示非漸近緊確的。 o(g(n)) = { f(n) : 對任意正常數(shù)c，存在正常數(shù)n0,使對所有n>=n0,有0<=f(n)<=c*g(n) }

ω記號：ω記號與Ω記號的關(guān)系和o記號與Ο記號的關(guān)系一樣，不在多說。

總之，可以這樣理解，Θ記號相當(dāng)于"=",Ο相當(dāng)于“<=",Ω相當(dāng)于”>=",o相當(dāng)于“<",ω相當(dāng)于">".這樣理解只用于區(qū)別不同漸近記號間的關(guān)系，其實每個漸近記號為一個函數(shù)集合，而非兩個數(shù)關(guān)系那樣的。

________________________________________-
對于任何數(shù)學(xué)函數(shù)，這三個記號可以用來度量其“漸近表現(xiàn)”，即當(dāng)趨于無窮大時的階的情況，這是算法分析中非常重要的概念。大家可以把它們分別想象成≤、≥和 =，分別估計了函數(shù)的漸近上界、漸近下界和準(zhǔn)確界。誠然，漸近關(guān)系和確切大小關(guān)系是有區(qū)別的，但當(dāng)問題規(guī)模很大時，忽略這種區(qū)別能大大降低算法分析的難度。

設(shè)函數(shù)f ( n )代表某一算法在輸入大小為n的情況下的工作量（效率），則在n趨向很大的時候，我們將f (n)與另一行為已知的函數(shù)g(n)進行比較：

1）如果=0，則稱f (n)在數(shù)量級上嚴(yán)格小于g(n)，記為f (n)=o( g(n))。

2）如果無窮，則稱f (n)在數(shù)量級上嚴(yán)格大于g(n)，記為f (n)=ω ( g(n))。

3）如果=c，這里c為非0常數(shù)，則稱f (n)在數(shù)量級上等于g(n)，即f (n)和g(n)是同一個數(shù)量級的函數(shù)，記為：f (n)=Θ( g(n))。

4）如果f (n)在數(shù)量級上小于或等于g(n)，則記為f (n)=O( g(n))。

5）如果f(n)在數(shù)量級上大于或等于g(n)，則記為f (n)=Ω( g(n))。

這里我們假定f (n)，g (n)是非負(fù)單調(diào)的，且極限存在。如果這個極限不存在，則無法對f (n)和g (n)進行比較。在進行此種計算時，一個經(jīng)常用到的技術(shù)是洛必達（L'Hopital）法則。該法則由17世紀(jì)法國數(shù)學(xué)家Guillaume de L'Hopital發(fā)現(xiàn)（也有人認(rèn)為是瑞士數(shù)學(xué)家Johann Bernoulli發(fā)現(xiàn)的）。該法則聲稱，兩個函數(shù)的比率極限等于兩個函數(shù)的導(dǎo)數(shù)的比率極限，這里當(dāng)然假定兩個函數(shù)的導(dǎo)數(shù)比率的極限存在，即有：