第八單元簡(jiǎn)單算法時(shí)空分析

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

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

1

3

7

8

4

3

61

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

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

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

第三行為k個(gè)整數(shù)表示對(duì)數(shù)組的k次查詢輸出格式：n行整數(shù),每行三個(gè)整數(shù)分別為:左邊最大值,右邊最大值,不包含自身的最大值輸出樣例：868輸出樣例：868818821378436157｛查詢了２次，第５個(gè)數(shù)和第７個(gè)數(shù)｝【分析】本題就是要找ｋ次最大值，根據(jù)我們的經(jīng)驗(yàn)，按照要求，提問(wèn)一次，找一次。就可以得到結(jié)果。這種查詢?cè)谝院蟮念}目中經(jīng)常用到。 本次給的例子還是用函數(shù)來(lái)將主程序給分成了幾段，再次強(qiáng)調(diào)這種寫(xiě)程序的思路。#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();//計(jì)算return0;}上面這個(gè)程序的時(shí)間復(fù)雜度是O(n*k)。題目給的n最大為100，k最大為50，所以最大計(jì)算次數(shù)為100*50。程序在1s之內(nèi)是肯定不會(huì)超時(shí)。我們來(lái)看【p1059】，數(shù)據(jù)量n到達(dá)了500000，k到了50000的數(shù)據(jù)量。用以上思路，最大計(jì)算次數(shù)是500000*50000，2.5*10^9。這么多運(yùn)算次數(shù)1s（10^8）肯定是不夠的。我們必須調(diào)整思路，對(duì)程序進(jìn)行相應(yīng)的優(yōu)化。我們上面程序?yàn)槭裁促M(fèi)時(shí)間，就是每次查詢都會(huì)重新查找一次，而每次的查找其實(shí)有很多重復(fù)計(jì)算。我們?cè)囍鴣?lái)避免這些重復(fù)，而要避免重復(fù)計(jì)算就是提前將可能要查詢的答案預(yù)先處理出后存儲(chǔ)起來(lái)，這樣查詢的時(shí)候，就不必重新查找了。我們定義leftmax[]，rightmax[]兩個(gè)數(shù)組，leftmax[i]表示第i個(gè)元素左邊的最大值是多少，rightmax[i]表示第i個(gè)元素右邊的最大值是多少。 我們?cè)诓樵冎皩eftmax和rightmax都計(jì)算出來(lái)，查詢的時(shí)候，只需要輸出結(jié)果即可。 那么如何預(yù)處理這兩個(gè)數(shù)組呢？如果還是每個(gè)leftmax[i]都用一次循環(huán)，那么這個(gè)程序的效率依然很差，我們需要用更高效率的代碼來(lái)求出這兩個(gè)數(shù)組。 我們觀察樣例：i12345678a13784361Leftmax01378888RightmaxRightmax自己去填。我們可以發(fā)現(xiàn)一個(gè)現(xiàn)象：leftmax[i]=max(a[i-1],leftmax[i-1])。這個(gè)式子可以讓我們用一重循環(huán)來(lái)求出leftmax。同理，肯定也能求出rightmax。這樣我們我們的代碼的運(yùn)算次數(shù)基本就是n+n+k。這樣肯定就不會(huì)超時(shí)。代碼下面給出，請(qǐng)理解這種思想。#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ù)組以后，他對(duì)數(shù)組之間的累加和特別感興趣，于是他就提出了要求數(shù)組元素之間的累加和的問(wèn)題。

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

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

從第4個(gè)元素到第9個(gè)元素的和就是

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