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

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

3、說是基本運算的原操作，以該基本操作重復執行的次數作為算法的時間量度。時間復雜度 時間復雜度： 一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。 例如在如下所示的兩個N*N矩陣相乘的算法中,“乘法”運算時“矩陣相乘問題”的基本操作。 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; 一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f (n)的極限值為不等于零的

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

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

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

7、）以相同的方法進行查找； 這個過程一直進行到查找成功或子表長度為 0 （說明線性表中沒有這個元素）為止。 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; 顯然，當有序線性表為順序存儲時才采用二分法查找，并且，二

8、分查找的效率要比順序查找高得多。可以證明，對于長度為 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;排序方法平均時間最壞時間輔助存儲選擇排序O(n2)O(n2)O(1)冒泡排序O(n2)O(n2)O

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

13、選用直接插入或冒泡排序為宜。 (3) 若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內部排序法中被認為是最好的方法 軍事機密軍事機密 Time Limit: 10 secondMemory Limit: 2 MB 問題描述我軍方截獲的信息由n（n30000）個數字組成，因為是敵國的高端秘密，所以一時不能被破獲。最原始的想法就是對這n個數進行從小到大排序，每個數都對應一個序號，然后對第i個是什么數感興趣，現在要求編程完成。 Input 第一行是n，第二行是n個截獲的數字，第三行是數字k，接著是k行要輸出數的序號。 Output

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

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

16、=1 to n do writeln(a1); delete(1); endp;類似于push,不過push是把小元素向上換，delete是把最小的刪掉后，把最后一個元素放上來，這樣就變成了把一個大元素向下放的過程，具體方法請自己思考。堆排序算法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堆的應用 果子合并在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并

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

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

20、合并n-1次。堆的應用用堆優化dijstra算法 例題：最小序列問題。例題：最小序列問題。 給定一個NN（N=100）的正整數矩陣。需要在矩陣中尋找一條從起始位置到終止位置的路徑(可沿上下左右四個方向)，并且要求路徑中經過的所有數字，其相鄰數字之差的絕對值之和最小。例題分析 這道題的基本算法很簡單，只要用Dijkstra算法求出從起始位置到終止位置的最短路徑即可。但這當中存在一個很大的問題：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 二叉搜索樹的構造過程 (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) 在二叉搜索樹上刪除一個結點也很方便。首先應搜索被刪除的元素。搜索刪除元素的方法與插入元素的做法類似，要求在從根結點往下搜索的過程中，記錄下當前元素的雙親結點，并用指針q指示。如果不存在該元素，那么顯示“No element with key”信息。

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