第八單元簡單算法時空分析

《第八單元簡單算法時空分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、第八單元簡單算法時空分析8.1算法分析的概念算法分析是指通過數(shù)學(xué)方法對一個算法的時間效率和空間效率經(jīng)行評估，并判斷該算法的優(yōu)劣。如果算法A的時空復(fù)雜度均低于算法B,那么我們認(rèn)為算法A優(yōu)于算法B。有時也有以空間換時間或者以時間換空間的算法，比如暴搜和記憶化搜索，前者是以吋間換空間的算法，而后者是以空間換時間。算法的設(shè)計要求：?正確性+程序不含語法錯誤；?程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格耍求的結(jié)果；?程序?qū)ι倚倪x擇的、典型的、苛刻的、帶有刁難性的兒組輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果；+程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格要求的結(jié)果。?可

2、讀性：有助于閱讀和交流、有助于對算法的理解、有助于對算法的調(diào)試和修改。?高效率和低存儲：處理速度快、存儲容雖小。8.2時間復(fù)雜度時間復(fù)雜度，從名字就可以知道，它表示的是算法運行的時間效率。一個算法運行所耗費的時間，除了與所用的計算軟、硬件環(huán)境有關(guān)外，主要取決于算法中指令重復(fù)執(zhí)行的次數(shù)，即語句的頻度相關(guān)。一個算法中所冇語句的頻度z和構(gòu)成了該算法的運行時間。以下為兒個代碼例子，我們依次分析它們的基本操作次數(shù)，并嘗試分析時間復(fù)雜度?！敬a分析例1】fact=1;for(inti=l;i<=n;i++)fact=fact*i;—?次乘法為-?個基本

3、操作，忽略i改變的吋間。共f(n)=n次基木操作。吋間復(fù)朵度為n【代碼分析的例子2】sum=0;for(inti=l;iv二n;i++)for(intj=l;j<=n;i++)〃這里的a[i][j]是二維數(shù)組，我們認(rèn)為a數(shù)組存儲了n^n個變量。sum=sum+a[i][j];基木操作：加法，乘法，忽略循環(huán)變最i和j的改變時間，共"2次基木操作。時間復(fù)雜度為於2【代碼分析的例子3】這段代碼實現(xiàn)的是1!+2!+……+n!sum=0;for(inti=l;i<=n;i++)fact=fact*jfact=l;for(intj=l;j<=i;i++

4、)sum:=sum+fact;第i次循環(huán)執(zhí)行了i個操作，總時間復(fù)雜度為1+2+3+…+n二n(n+l)/2。這個式了我們可以約等于22/2。如果式子再長一點，怎么辦？比較【例2］和【例3】，【例2］執(zhí)行了f(n)E2次基本操作,【例3］執(zhí)行了g(n)="2/2次基本操作。那個算法好呢？算法二好，因為g(n)

5、2/2。我們知道，它們的增長情況一樣。如何表示“增長情況”？把f(n)和g(n)變成“漸進(jìn)”形式，然后肓接比較。如何變成“漸進(jìn)'形式？1)只保留最“大巧頁；2)忽略系數(shù)例1：3nA4+8nA2+n+2的漸進(jìn)時間復(fù)雜度為nA4例2：2A(n+l)+n*100+5的漸進(jìn)時間復(fù)雜度為2An(為什么n+1變成了n?)有時候復(fù)雜度分析不是萬能的，或者說有時候不知道最壞情況是多少。我們看一下OJ【P1029】一個數(shù)n,如果它是奇數(shù)則變換到3n+l,否則變換到n/2。給一個數(shù)n,不停的變換下去，經(jīng)過幾步變成1?你知道它的運行時間嗎?!反正我不知道，這是個

6、著名的停機(jī)問題所以，我們在分析時間復(fù)雜度的時候，只分析上限，而不管實際運行時間。若n充分大時

7、f(n)

8、v=c

9、g(n)

10、,其中c為某常數(shù)。記f(n)=O(g(n)),表示g(n)為f(n)的漸進(jìn)上限例1：5nA2+3n+l=0(nA2)例2：223=0(23)山于上限有無限多個，我們希望它盡量粕確。否則我們的分析就過于悲觀了，實際算法沒那么糟糕。這就是我們常說的時間復(fù)雜度，一般用最壞的時間復(fù)雜度來衡最一個程序的效率。常見的復(fù)雜度等級：絕大多數(shù)算法都定多項式算法OO(nAt),t是常數(shù)OO(log(t)n),t是常數(shù)OO(loglogn),

11、奇怪嗎？后面會遇到一個O兩個多項式時間復(fù)雜度的積仍是多項式的復(fù)雜度效率排序，越靠左邊，效率越高。0(1)

12、表示i的N次幕。(指數(shù)級)O(N!)：表示N的階乘，即N!=1*2*3*...*No(階乘級)強(qiáng)調(diào)：這里的logn的對數(shù)底不是10,而是2,也就是10g2(n)o這個是要記住的。