《算法設計與分析》一一2.2 函數的漸近增長率

2.2　函數的漸近增長率

根據1.3節的定義，算法的最壞情況時間複雜度是規模n的函數。由于n是一個變量，這就給比較算法的優劣帶來一個問題：算法1和算法2在規模值n取不同值的時候，它們的優劣可能是不一樣的。常見的情況是，有一些複雜的算法在小規模的時候無優勢甚至有劣勢，但是它們的優勢将在問題規模很大的時候顯現出來。我們在進行算法分析的時候，更關心問題規模很大時算法的表現。但是何謂規模大，對于不同的算法而言又千差萬别。有的算法可能在幾千的規模上就比同類算法有優勢，而有的算法可能需要到百萬級的規模才能顯現優勢。

正是針對算法分析中的上述困難，我們引入函數的漸近增長率(asymptotic growth rate)概念，其中：

●增長率的概念使得我們集中關注算法在規模較大時候的性能表現，它關注的不是代價函數的具體的值，而是代價函數的值随規模增長的速度。因而不管開始的優劣如何，增長率較快的函數在面對大規模輸入的時候值會變得更大。

●漸近的概念幫我們處理了不同算法對于 “大規模”的含義有不同解讀的問題，它關注的是問題規模趨于無窮時算法代價的變化情況。

我們引入3組共5個不同的記号來描述函數的漸近增長率之間的關系，它們是o和o 、Ω 和ω 、Θ。我們首先給出使用極限語言的定義，在此基礎上給出基于求極限的判别方法。在這3組記号中，o和o的定義是基礎，這兩個符号之間的差别是了解其定義的重點。首先給出這兩個記号的定義。

定義2.2（f(n)=o(g(n))）

●o(g(n)) ={f(n)：存在常數c>0和n0>0，滿足0≤f(n)≤cg(n)對所有n≥n0均成立}。

●f(n)=o(g(n)) iff limn→∞f(n)g(n)=c<∞。

定義2.3（f(n)=o(g(n))）

●o(g(n)) ={f(n)：對任意常數c>0，均存在常數n0>0，滿足0≤f(n)●f(n)=o(g(n)) iff limn→∞f(n)g(n)=0。

不嚴格地說，f(n)=o(g(n))描述的是當問題規模充分大的時候，函數f(n)的增長率不會超過g(n)的增長率。與記号o(g(n))相比，f(n)=o(g(n))雖然同樣表示函數f(n)的增長率不會超過g(n)的增長率，但是它的要求更強。f(n)=o(g(n))強調函數f(n)和g(n)在增長率方面有一種“實質性的差距”：總可以通過增加問題規模n，使得函數f(n)和g(n)之間有任意大的差距。

與上述定義對偶，我們有下面兩個定義。

定義2.4（f(n)=Ω(g(n))）

●Ω(g(n)) ={f(n)：存在常數c>0和n0>0，滿足0≤cg(n)≤f(n)對所有n≥n0均成立}。

●f(n)=Ω(g(n)) iff limn→∞f(n)g(n)=c>0（c也可以為∞）。

定義2.5（f(n)=ω(g(n))）

●ω(g(n)) ={f(n)：對任意常數c>0，均存在常數n0>0，滿足0≤cg(n)●f(n)=ω(g(n)) iff limn→∞f(n)g(n)=∞。

與o和o的定義對偶，f(n)=Ω(g(n))描述的是随着問題規模的增大，函數f(n)的增長率不會低于g(n)的增長率；而f(n)=ω(g(n))同樣強調函數f(n)和g(n)在增長率方面有一種“實質性的差距”：總可以通過規模n的增大，使得f(n)和g(n)有任意大的差距。

另外，我們可以定義f(n)=Θ(g(n))，它表示f(n)和g(n)的增長率處于“同一水準”。

定義2.6（f(n)=Θ(g(n))）

●Θ(g(n)) ={f(n)：存在常數c1>0，c2>0和n0>0，滿足0≤c1g(n)≤f(n)≤c2g(n)對所有n≥n0均成立}。

●f(n)=Θ(g(n)) iff limn→∞f(n)g(n)=c，這裡 0根據上述定義，我們很容易驗證：

●o、Ω、Θ、o、ω這5種關系均滿足傳遞性。

●o、Ω、Θ這3種關系滿足自反性。

●Θ是一個等價關系。

●f(n)=Θ(g(n)) iff f(n)=o(g(n))且f(n)=Ω(g(n))。

●o、 o和Ω、ω之間有一種對偶的關系，即f=o(g) iff g=Ω(f),f=o(g) iff g=ω(f)。

這些性質的證明留作習題。