時(shí)間空間復(fù)雜度

1、時(shí)間空間復(fù)雜度算法效率的度量 算法執(zhí)行時(shí)間需要通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量。而度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法：事后統(tǒng)計(jì)的方法 可以利用計(jì)算機(jī)的內(nèi)部計(jì)時(shí)功能，先把程序編寫好運(yùn)行一下進(jìn)行計(jì)時(shí)。不過這種方法有兩個(gè)缺陷： 一是必須先編制好程序并運(yùn)行； 二是所得出的時(shí)間統(tǒng)計(jì)量依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣性。 事先分析估算的方法 A）依據(jù)的算法選用何種策略； B）問題的規(guī)模。例如求100以內(nèi)還是10000以內(nèi)的素?cái)?shù)； C）書寫程序的語言。對(duì)于同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低； D）編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量； E）機(jī)器執(zhí)行指

2、令的速度。 顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行時(shí)，效率均不相同。 這表明使用絕對(duì)的時(shí)間單位衡量算法的效這表明使用絕對(duì)的時(shí)間單位衡量算法的效率是不合適的。率是不合適的。撇開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)的函數(shù)。 一個(gè)算法是由控制結(jié)構(gòu)控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。 為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對(duì)于所研究的問題（或算法類型）來

3、說是基本運(yùn)算的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。時(shí)間復(fù)雜度 時(shí)間復(fù)雜度： 一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)。 例如在如下所示的兩個(gè)N*N矩陣相乘的算法中,“乘法”運(yùn)算時(shí)“矩陣相乘問題”的基本操作。 for i:=1 to n do for j:=1 to n do begin ci,j:=0; for k:=1 to n do ci,j:=ci,j+ai,k*bk,j end; 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T(n)/f (n)的極限值為不等于零的

4、常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n),稱O(f(n) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。 整個(gè)算法的執(zhí)行時(shí)間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù)N成正比，記T(N)=O(N)?！癘”的形式定義為：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則xn=O(f(n)表示存在一個(gè)正的常數(shù)M，使得當(dāng)n=n0時(shí)都滿足|xn|=M|f(n)|空間復(fù)雜度 是程序運(yùn)行所以需要的額外額外消耗存儲(chǔ)空間,一般的遞歸算法就要有o(n)的空間復(fù)雜度了,簡單說就是遞歸集算時(shí)通常是反復(fù)調(diào)用同一個(gè)方法，遞歸n次，就需要n個(gè)空間。（這個(gè)空間到底多大？我們姑且把它當(dāng)作每次調(diào)用時(shí)分配的內(nèi)存大小，到底多大，它

5、自己確定） 我們?cè)谂凶x算法的優(yōu)劣時(shí)，往往是綜合考慮時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)因素，一般是希望能夠找到兩個(gè)都省的方法，但事實(shí)上我們往往需要犧牲時(shí)間復(fù)雜度來成全空間，或犧牲空間來節(jié)省時(shí)間。因此我們需要根據(jù)題目要求，選擇側(cè)重節(jié)省的因素。 更多的時(shí)候由于空間的耗費(fèi)我們一般可以容忍，所以我們會(huì)更關(guān)注時(shí)間復(fù)雜度對(duì)算法的影響。 例:給出一個(gè)還有n個(gè)數(shù)的有序序列，要求查給定的一個(gè)數(shù)x是否在序列中，若在則給出所在序列中所處的位置。輸入：第一行輸入兩個(gè)數(shù)n和x 第二行為n個(gè)數(shù)輸出：x在序列中所處的位置的序號(hào)樣例：input： 6 61 12 35 58 60 61 100 output： 5順序查找 從線性表的第

6、一個(gè)元素開始，依次將線性表中的元素被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。procedure search2(num:longint); var i,j:longint; begin for i:=1 to n do if ai=num then writeln(i);end; 二分查找法 若中間項(xiàng)的值等于 x ，則說明查到，查找結(jié)束。 若 x 小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找； 若 x 大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分

7、）以相同的方法進(jìn)行查找； 這個(gè)過程一直進(jìn)行到查找成功或子表長度為 0 （說明線性表中沒有這個(gè)元素）為止。 procedure search(num:longint); var top,end1,mid:longint; begin top:=0;end1:=n; if end-top1)and(atopnum) do begin mid:=(top+end1) div 2; if num=amid then top:=mid else end1:=mid; end; if atop=num then writeln(top); end; 顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才采用二分法查找，并且，二

8、分查找的效率要比順序查找高得多?？梢宰C明，對(duì)于長度為 n 的有序線性表，在最壞情況下，二分查找只需要比較 log 2 n 次，而順序查找需要比較 n 次。 選擇排序：Procedure selectsort (var r:arraytype); begin for i:=1 to n-1 do Begin k:=i; for j:=i+1 to n do begin if rjrk then k:=j end; if ki then begin temp:=ri; ri:=rk; rk:=temp; end; end; end; end; 冒泡排序：Procedure selectsort (

9、var a:arraytype);beginfor i:=1 to n-1 do for j:=1 to n-i do if ajaj+1 then begin temp:=aj; aj:=aj+1; aj+1:=temp; end;end; 插入排序： procedure inssort(var r:arraytype); begin r0:=-maxint; for i:=2 to n do begin j:=i-1; x:=ri; while x0 do begin write(i:6); bi:-bi-1; end; writeln;歸并排序：procedure mergesort(s

10、,t:integer); var m,i,j,k:integer; begin if s=t then exit; m:=(s+t) div 2; mergesort(s,m); mergesort(m+1,t); i:=s; j:=m+1; k:=s; while(i=m) and (j=t) do begin if ai=aj then begin rk:=ai; inc(i); inc(k); end else begin rk:=ai; inc(j); inc(k); end; end; while i=m do begin rk:=ai; inc(i); inc(k); end; w

11、hile j=t do begin rk:=aj; inc(j); inc(k); end; for i:=s to do ai:=ri; end;快速排序：procedure qsort( l,r:longint);Var i,j,m,p,k:longint;begin m:=arandom(r-l)+l; i:=l;j:=r; repeat while aim do dec(j); if ij; if lj then qsort(l,j); if ir then qsort(i,r);end;排序方法平均時(shí)間最壞時(shí)間輔助存儲(chǔ)選擇排序O(n2)O(n2)O(1)冒泡排序O(n2)O(n2)O

12、(1)計(jì)數(shù)排序O(n)O(n)0歸并排序O(nlog2n) O(nlog2n)O(n)插入排序O(n2)O(n2)O(1)快速排序O(nlog2n) O(nlog2n)O(log2n)幾種排序算法的比較和選擇 選取排序方法需要考慮的因素： (1) 待排序的元素?cái)?shù)目n； (2) 元素本身信息量的大??； (3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況； (4) 語言工具的條件，輔助空間的大小等。 1) 若n較小(n = 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動(dòng)操作較直接選擇排序多，因而當(dāng)記錄本身信息量較大時(shí)，用直接選擇排序較好。 (2) 若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則

13、選用直接插入或冒泡排序?yàn)橐恕?(3) 若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內(nèi)部排序法中被認(rèn)為是最好的方法 軍事機(jī)密軍事機(jī)密 Time Limit: 10 secondMemory Limit: 2 MB 問題描述我軍方截獲的信息由n（n30000）個(gè)數(shù)字組成，因?yàn)槭菙硣母叨嗣孛?，所以一時(shí)不能被破獲。最原始的想法就是對(duì)這n個(gè)數(shù)進(jìn)行從小到大排序，每個(gè)數(shù)都對(duì)應(yīng)一個(gè)序號(hào)，然后對(duì)第i個(gè)是什么數(shù)感興趣，現(xiàn)在要求編程完成。 Input 第一行是n，第二行是n個(gè)截獲的數(shù)字，第三行是數(shù)字k，接著是k行要輸出數(shù)的序號(hào)。 Output

14、k行序號(hào)所對(duì)應(yīng)的數(shù)字。 輸油管道問題輸油管道問題 Time Limit: 10 secondMemory Limit: 2 MB問題描述某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過一個(gè)有n 口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置,即它們的x 坐標(biāo)（東西向）和y 坐標(biāo)（南北向）,應(yīng)如何確定主管道的最優(yōu)位置, 即使各油井到主管道之間的輸油管道長度總和最小的位置?證明可在線性時(shí)間內(nèi)確定主管道的最優(yōu)位置。編程任務(wù)：給定n 口油井的位置,編程計(jì)算各油井到主管道之間的輸油管道最小長度總和。Input由文件input.txt 提供輸入

15、數(shù)據(jù)。文件的第1 行是油井?dāng)?shù)n，1n10000。接下來n 行是油井的位置，每行2個(gè)整數(shù)x和y，-10000 x，y10000。 Output程序運(yùn)行結(jié)束時(shí)，將計(jì)算結(jié)果輸出到文件output.txt 中。文件的第1 行中的數(shù)是油井到主管道之間的輸油管道最小長度總和堆 堆是一種特殊的二叉樹 它滿足V(左孩子)V(右孩子)或V(左孩子)V(根)ai do swap(i,i div 2); i:=i div 2; endw;end;堆選擇與維出堆頂節(jié)點(diǎn)7127 37288338 68一、取出二、調(diào)整算法描述（堆排序） procedure sort; build; for i:

16、=1 to n do writeln(a1); delete(1); endp;類似于push,不過push是把小元素向上換，delete是把最小的刪掉后，把最后一個(gè)元素放上來，這樣就變成了把一個(gè)大元素向下放的過程，具體方法請(qǐng)自己思考。堆排序算法PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=rk.key;finish:=false t:=rk; while (j=m) and not finish do if (jrj+1.key) then j:=j+1; If x=rj.key then finish:=true Els

17、e ri:=rj; i:=j; j:=2*I ri:=tendPPROC heapsort(var r:listtype);For i:=n/2 downto 1 shift(r,I,n);For i:=n downto 2 do r1與與ri交換交換; shift(r,1,i-1) endP堆的應(yīng)用 果子合并在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并

18、所耗體力之和。 因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。 例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15?？梢宰C明15為最小的體力耗費(fèi)值。 堆的應(yīng)用 【輸入文件】 輸入文件fruit.in包括兩行，第一行是一個(gè)整數(shù)n(1n=10000)，表示果子的種類數(shù)。第二行包含n個(gè)

19、整數(shù)，用空格分隔，第i個(gè)整數(shù)ai(1ai=20000)是第i種果子的數(shù)目。 【輸出文件】 輸出文件fruit.out包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于231。 堆的應(yīng)用 很明顯，這道題是一道貪心的題目，可以證明，每次取最小的兩堆合并會(huì)使得最后的體力值最小。 那么，這道題的問題就在于怎么找最小的兩堆果子了。 注意到，每次合并完果子會(huì)刪掉兩堆，并添加一堆新的，如果采用線性表，時(shí)間復(fù)雜度將高達(dá)O（N2），對(duì)于N=20000是不夠的。 所以，我們考慮用小根堆優(yōu)化。堆的應(yīng)用 算法： 建立空堆 每讀入一個(gè)數(shù)插入堆中 每次取兩個(gè)堆頂元素合并，并插入合并后的數(shù)，總共

20、合并n-1次。堆的應(yīng)用用堆優(yōu)化dijstra算法 例題：最小序列問題。例題：最小序列問題。 給定一個(gè)NN（N=100）的正整數(shù)矩陣。需要在矩陣中尋找一條從起始位置到終止位置的路徑(可沿上下左右四個(gè)方向)，并且要求路徑中經(jīng)過的所有數(shù)字，其相鄰數(shù)字之差的絕對(duì)值之和最小。例題分析 這道題的基本算法很簡單，只要用Dijkstra算法求出從起始位置到終止位置的最短路徑即可。但這當(dāng)中存在一個(gè)很大的問題：NRoot; (b) q=p; p=p-Rchild; (c) q=p; p=p-Rchild; (d) r=NewNode2(x); q-Rchild=r2836332125pq(a)2836332125

21、q(b)p2836332125q(c)p283633432125qr(d)圖83 二叉搜索樹的構(gòu)造過程 (a) 空樹；(b) 插入28；(c) 插入21；(d) 插入25；(e) 插入36；(f) 插入33；(g) 插入43283633432125(g)2836332125(f)28362125(e)282125(d)2821(c)28(b)(a) 在二叉搜索樹上刪除一個(gè)結(jié)點(diǎn)也很方便。首先應(yīng)搜索被刪除的元素。搜索刪除元素的方法與插入元素的做法類似，要求在從根結(jié)點(diǎn)往下搜索的過程中，記錄下當(dāng)前元素的雙親結(jié)點(diǎn)，并用指針q指示。如果不存在該元素，那么顯示“No element with key”信息。

22、如果存在待刪除的結(jié)點(diǎn)，設(shè)其由指針p指示，則刪除結(jié)點(diǎn)*p的操作可分下面三種情況討論。二叉搜索樹的刪除二叉搜索樹的刪除1）沒有兒子，即為葉節(jié)點(diǎn)。直接把父節(jié)點(diǎn)的對(duì)應(yīng)兒子指針設(shè)為NULL，刪除兒子節(jié)點(diǎn)就OK了。2）只有一個(gè)兒子。那么把父節(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子，刪除兒子節(jié)點(diǎn)也OK了。二叉搜索樹的刪除二叉搜索樹的刪除二叉搜索樹的刪除二叉搜索樹的刪除3）有兩個(gè)兒子。這是最麻煩的情況，因?yàn)閯h除節(jié)點(diǎn)之后，還要保證滿足搜索二叉樹的結(jié)構(gòu)。其實(shí)也比較容易，我們可以選擇左兒子中的最大元素或者右兒子中的最小元素放到待刪除節(jié)點(diǎn)的位置，就可以保證結(jié)構(gòu)的不變。當(dāng)然，要記得調(diào)整子樹，畢竟又出現(xiàn)了節(jié)點(diǎn)刪除。這里選擇左兒子的最大元素，將它放到待刪節(jié)點(diǎn)的位置。左兒子的