第八單元簡單算法時空分析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é)果。可讀性：有助于閱讀和交流、有助于對算法的理解、有助于對算法的調(diào)試和修改。高效率和低存儲：處理速度快、存儲容量小。8.2時間復(fù)雜度時間復(fù)雜度，從名字就可以知道，它表示的是算法運(yùn)行的時間效率。一個算法運(yùn)行所耗費的時間，除了與所用的計算軟、硬件環(huán)境有關(guān)外，主要取決于算法中指令重復(fù)執(zhí)行的次數(shù)，即語句的頻度相關(guān)。一個算法中所有語句的頻度之和構(gòu)成了該算法的運(yùn)行時間。以下為幾個代碼例子，我們依次分析它們的基本操作次數(shù)，并嘗試分析時間復(fù)雜度。【代碼分析例1】fact=1;for(inti=1;i<=n;i++)fact=fact*i;一次乘法為一個基本操作，忽略i改變的時間。共f(n)=n次基本操作。時間復(fù)雜度為n【代碼分析的例子2】sum=0;for(inti=1;i<=n;i++)for(intj=1;j<=n;i++) //這里的a[i][j]是二維數(shù)組，我們認(rèn)為a數(shù)組存儲了n*n個變量。sum=sum+a[i][j];基本操作：加法，乘法，忽略循環(huán)變量i和j的改變時間，共n^2次基本操作。時間復(fù)雜度為n^2【代碼分析的例子3】這段代碼實現(xiàn)的是1!+2!+……+n!sum=0;for(inti=1;i<=n;i++){fact=1;for(intj=1;j<=i;i++)fact=fact*jsum:=sum+fact;}第i次循環(huán)執(zhí)行了i個操作,總時間復(fù)雜度為1+2+3+…+n=n(n+1)/2。這個式子我們可以約等于n^2/2。如果式子再長一點，怎么辦？比較【例2】和【例3】，【例2】執(zhí)行了f(n)=n^2次基本操作，【例3】執(zhí)行了g(n)=n^2/2次基本操作。那個算法好呢？算法二好，因為g(n)<f(n)增長情況呢？n擴(kuò)大10倍，f(n)擴(kuò)大100倍，g(n)也擴(kuò)大100倍。兩個算法的增長情況一樣！我們其實更在乎數(shù)據(jù)規(guī)模擴(kuò)大，時間隨著n增加的漸進(jìn)時間復(fù)雜度。對于例2和例3，根據(jù)其執(zhí)行次數(shù)與n的關(guān)系：f(n)=n^2和g(n)=n^2/2。我們知道，它們的增長情況一樣。如何表示“增長情況”？把f(n)和g(n)變成“漸進(jìn)”形式，然后直接比較。如何變成“漸進(jìn)”形式？1）只保留最“大”項；2）忽略系數(shù)例1：3n^4+8n^2+n+2的漸進(jìn)時間復(fù)雜度為n^4例2：2^(n+1)+n*100+5的漸進(jìn)時間復(fù)雜度為2^n(為什么n+1變成了n？)有時候復(fù)雜度分析不是萬能的，或者說有時候不知道最壞情況是多少。我們看一下OJ【P1029】一個數(shù)n，如果它是奇數(shù)則變換到3n+1，否則變換到n/2。給一個數(shù)n，不停的變換下去，經(jīng)過幾步變成1？你知道它的運(yùn)行時間嗎?!反正我不知道，這是個著名的停機(jī)問題所以，我們在分析時間復(fù)雜度的時候，只分析上限，而不管實際運(yùn)行時間。若n充分大時|f(n)|<=c|g(n)|，其中c為某常數(shù)。記f(n)=O(g(n))，表示g(n)為f(n)的漸進(jìn)上限例1：5n^2+3n+1=O(n^2)例2：2n^3=O(n^3)由于上限有無限多個，我們希望它盡量精確。否則我們的分析就過于悲觀了，實際算法沒那么糟糕。 這就是我們常說的時間復(fù)雜度，一般用最壞的時間復(fù)雜度來衡量一個程序的效率。常見的復(fù)雜度等級：絕大多數(shù)算法都是多項式算法O(n^t)，t是常數(shù)O(log(t)n),t是常數(shù)O(loglogn),奇怪嗎？后面會遇到一個兩個多項式時間復(fù)雜度的積仍是多項式的復(fù)雜度效率排序，越靠左邊，效率越高。O(1)<O(loglogn)<O(logn)<O(sqrt(n))<O(n)O(n)<O(nloglogn)<O(nlogn)<O(n^2)O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)O(1)：表示復(fù)雜度為常數(shù)。(常數(shù)級)O(N)：表示復(fù)雜度為N。(線性級)O(N^i)：N^i表示N的i次冪。(多項式級)O(sqrt(N))：表示根號N，即N開方。(多項式級)O(logN)：表示以2為底數(shù)N的對數(shù)。(對數(shù)級)O(i^N)：表示i的N次冪。(指數(shù)級)O(N!)：表示N的階乘，即N!=1*2*3*…*N。(階乘級)強(qiáng)調(diào)：這里的logn的對數(shù)底不是10，而是2，也就是log2(n)。這個是要記住的。以后再學(xué)相應(yīng)的算法，我們就要學(xué)著分析算法的時間效率。考試時的參考：我們知道，考試時1s的運(yùn)行次數(shù)是10^8次，那么我們就要根據(jù)數(shù)據(jù)規(guī)模來判斷算法。如果數(shù)據(jù)規(guī)模在100以內(nèi)，三重循環(huán)就不會超時。如果數(shù)據(jù)規(guī)模在9000以內(nèi)，二重循環(huán)就不會超時。如果數(shù)據(jù)規(guī)模在10000以上，你的程序就必須要考慮1重循環(huán)了，或者n*logn的算法。8.3空間復(fù)雜度空間復(fù)雜度指的是實現(xiàn)算法的空間開銷，同樣使用多項式來表示。最主要的體現(xiàn)就是數(shù)組，數(shù)組的大小即為該算法的空間復(fù)雜度。（1）計算機(jī)基本計量單位計算機(jī)最基本單位為字節(jié)(Byte)，計算機(jī)最小的單位是位（bit）一個int數(shù)據(jù)占8個B。1024B=2^10B=1KB1024KB=2^20B=1MB1024MB=2^30B=1GB50M的內(nèi)存限制可以定義50*1024*1024/4個int變量約等于1000萬長度的int數(shù)組（2）一般的估算說到空間復(fù)雜度，其實主要擔(dān)心就是會不會爆內(nèi)存。這里有一個很簡單的方法就可以確定：在C/C++里面有sizeof()這個函數(shù)(Pascal里面應(yīng)該也有)，它返回的是變量的字節(jié)數(shù)，比如說sizeof(int)，就會告訴你int所占用的空間大小；sizeof(a)，其中a是一個數(shù)組，這時返回的就是數(shù)組a的總空間大小。對于一個已經(jīng)寫好的程序，我們把它所有靜態(tài)數(shù)組的sizeof()全部加起來，然后除上10^6，得到的數(shù)字就是所占用的靜態(tài)內(nèi)存MB數(shù)，有沒有爆內(nèi)存自然一目了然。8.4空間換時間實例現(xiàn)代計算機(jī)的內(nèi)存空間的增加要超過運(yùn)算速度增加，我們現(xiàn)在的題目，一般都是空間不會超，時間可能會超。所以，我們更多的考慮算法的時候，一般會考慮用空間換時間來將問題。【P1058】陶陶剛學(xué)了數(shù)組，并且他對查找一維數(shù)組中的最大值特別感興趣，于是，他就產(chǎn)生了疑問：能不能找到數(shù)組中某個元素的左邊的最大值、右邊的最大值和不包含自身的最大值。

例如：一個數(shù)組共8個元素，

1

3

7

8

4

3

61

第5個數(shù)（4）左邊的最大值是8

右邊最大值是6，不包含自身的最大值是8輸入格式：第一行為n,k(n表示數(shù)組含有n個元素,k表示有k次查詢)(n<=100,k<=50)

第二行為n個整數(shù),表示數(shù)組的n個元素

第三行為k個整數(shù)表示對數(shù)組的k次查詢輸出格式：n行整數(shù),每行三個整數(shù)分別為:左邊最大值,右邊最大值,不包含自身的最大值輸出樣例：868輸出樣例：868818821378436157｛查詢了２次，第５個數(shù)和第７個數(shù)｝【分析】本題就是要找ｋ次最大值，根據(jù)我們的經(jīng)驗，按照要求，提問一次，找一次。就可以得到結(jié)果。這種查詢在以后的題目中經(jīng)常用到。 本次給的例子還是用函數(shù)來將主程序給分成了幾段，再次強(qiáng)調(diào)這種寫程序的思路。#include<iostream>usingnamespacestd;intn,k,m,a[110],max3;voidinit(){ cin>>n>>m; for(inti=1;i<=n;i++)cin>>a[i];}voidwork(){for(inti=0;i<m;i++){ cin>>k; intmaxleft=-10000,maxright=-10000;for(intj=1;j<=k-1;j++)if(maxleft<a[j])maxleft=a[j];for(intj=k+1;j<=n;j++)if(maxright<a[j])maxright=a[j]; if(maxleft>maxright)max3=maxleft; elsemax3=maxright; cout<<maxleft<<''<<maxright<<''<<max3<<endl; }}intmain(){init();//讀入數(shù)據(jù)work();//計算return0;}上面這個程序的時間復(fù)雜度是O(n*k)。題目給的n最大為100，k最大為50，所以最大計算次數(shù)為100*50。程序在1s之內(nèi)是肯定不會超時。我們來看【p1059】，數(shù)據(jù)量n到達(dá)了500000，k到了50000的數(shù)據(jù)量。用以上思路，最大計算次數(shù)是500000*50000，2.5*10^9。這么多運(yùn)算次數(shù)1s（10^8）肯定是不夠的。我們必須調(diào)整思路，對程序進(jìn)行相應(yīng)的優(yōu)化。我們上面程序為什么費時間，就是每次查詢都會重新查找一次，而每次的查找其實有很多重復(fù)計算。我們試著來避免這些重復(fù)，而要避免重復(fù)計算就是提前將可能要查詢的答案預(yù)先處理出后存儲起來，這樣查詢的時候，就不必重新查找了。我們定義leftmax[]，rightmax[]兩個數(shù)組，leftmax[i]表示第i個元素左邊的最大值是多少，rightmax[i]表示第i個元素右邊的最大值是多少。 我們在查詢之前將leftmax和rightmax都計算出來，查詢的時候，只需要輸出結(jié)果即可。 那么如何預(yù)處理這兩個數(shù)組呢？如果還是每個leftmax[i]都用一次循環(huán)，那么這個程序的效率依然很差，我們需要用更高效率的代碼來求出這兩個數(shù)組。 我們觀察樣例：i12345678a13784361Leftmax01378888RightmaxRightmax自己去填。我們可以發(fā)現(xiàn)一個現(xiàn)象：leftmax[i]=max(a[i-1],leftmax[i-1])。這個式子可以讓我們用一重循環(huán)來求出leftmax。同理，肯定也能求出rightmax。這樣我們我們的代碼的運(yùn)算次數(shù)基本就是n+n+k。這樣肯定就不會超時。代碼下面給出，請理解這種思想。#include<iostream>usingnamespacestd;inta[501000],leftmax[501000],rightmax[501000];intn,k,m,maxx=0;voidinit(){cin>>n>>k;a[0]=0;a[n+1]=0;for(inti=1;i<=n;i++)cin>>a[i];}voidwork(){for(inti=1;i<=n;i++)//預(yù)處理leftmaxif(a[i-1]>=leftmax[i-1])leftmax[i]=a[i-1];elseleftmax[i]=leftmax[i-1];for(inti=n;i>=1;i--)//預(yù)處理rightmaxif(a[i+1]>=rightmax[i+1])rightmax[i]=a[i+1];elserightmax[i]=rightmax[i+1];for(inti=1;i<=k;i++){cin>>m;if(leftmax[m]>rightmax[m])maxx=leftmax[m];elsemaxx=rightmax[m];cout<<leftmax[m]<<''<<rightmax[m]<<''<<maxx<<endl;}}intmain(){init();work();return0;}【P1061】數(shù)組求和陶陶學(xué)了數(shù)組以后，他對數(shù)組之間的累加和特別感興趣，于是他就提出了要求數(shù)組元素之間的累加和的問題。

例如：現(xiàn)在有長度為10的數(shù)組：3251453782

從第2個元素到第5個元素的和就是2+5+1+4=12

從第4個元素到第9個元素的和就是

1+4+5+3+7+8=28輸入格式；第一行nk兩個正整數(shù),分別表示數(shù)組有n個元素,k次求和查詢(0<=n,k<=1000)第二行為n個整數(shù)數(shù)組的n個元素以下有k行,每行兩個元素,為求和的起點和終點輸出格式：k行,每行為起點到終點的和.【分析】這道題的n和k最大只為1000，所以，我們可以用兩重循環(huán)根據(jù)每次查詢來完成此題，到這里，我們應(yīng)該具備這種能力。并參考上面代碼的形式，用函數(shù)來寫。【P1062】本題是1061的加強(qiáng)版，n和k的上限到了100000。用兩重循環(huán)寫的話，會超時的一塌糊涂，我們必須嘗試調(diào)整思路，進(jìn)行優(yōu)化。 在求部分和的時候，經(jīng)常用的思想就是線轉(zhuǎn)換點的思想。我們提前預(yù)處理一個sum數(shù)組，sum[i]表示前i項的累加和。i12345678910a3251453782Sum351011152023303840如果我們要求第2項到第5項的累加和只需要做一次減法即可：sum[5]-s[1]=12同理，第4項到第9項的累加和就是sum[9]-sum[3]=28。在本例中，我們利用提前預(yù)處理一個sum數(shù)組，就可以讓求部分區(qū)間累加和的那重循環(huán)給省略掉，這樣極大的提高了程序的效率。這就是一種典型的空間換時間思想。 以上兩道題的數(shù)據(jù)量加大后，我們都