1、第1章緒論1.1 什么是數據結構1.2 基本概念和術語1.3 抽象數據類型的表示和實現(xiàn)1.4 算法和算法分析1第一章：緒論1.4 算法和算法分析2程序設計的實質：好算法好結構算法是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉換為輸出的計算步驟。D.E.Knuth算法是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列。此外，其具有如下五個重要特性有窮性確定性輸入輸出可行性計算機程序設計藝術1.4 算法和算法分析3正確性原則上應該證明算法對于任意合理的輸入都正確實際中常用推理法證明時間代價(時間復雜度)必須拋棄的評價指標算法運行的實際執(zhí)行時間運行過程中所

2、執(zhí)行的指令條數運行過程中程序循環(huán)的次數空間代價 (空間復雜度)需要使用或開辟多少額外的空間最優(yōu)性算法效率的評價標準1.4 算法和算法分析4算法效率的度量一個高級語言程序的運行時間取決下列因素：算法策略問題規(guī)模書寫程序的語言編譯程序所產生的機器代碼的質量機器執(zhí)行指令的速度程序執(zhí)行時間的二種常用度量方法事后統(tǒng)計方法事前分析估算法1.4 算法和算法分析5算法效率的度量從算法中選取對于所研究的問題（或算法類型）來說是基本運算的原操作，其重復執(zhí)行次數和算法的執(zhí)行時間成正比。求出該算法執(zhí)行原操作用的次數（頻度），并以此作為算法的時間量度 撇開有關執(zhí)行平臺的硬軟件因素（如計算機速度、編譯程序等），算法是由控

3、制結構和原操作組成 。1.4 算法和算法分析6算法效率的度量當問題規(guī)模以某種單位由1增至n時，對應算法所耗費的時間也以某種單位由f(1)增至f(n)，這時，我們稱該算法的時間代價 f(n) 。時間單位則是稱之為基本操作的原操作。多數情況下，以最深層循環(huán)內的原操作作為基本操作。事前估計法并不要求精確求出f(n) ，而要求給出能反映基本操作的執(zhí)行次數隨問題規(guī)模的增長速率的某個近似函數：T(n)=O(f(n)稱O(f(n)為近似時間復雜度，簡稱時間復雜度。7算法效率的度量漸進符號“大O”的定義： 當且僅當存在一個正的常數 C，使得對所有的 n n0 ，有 f(n) Cg(n)，則 f(n) = O(

4、g(n)100n+6=O(n) /* 100n+6101n for n6 */10n2+4n+2=O(n2) /* 10n2+4n+211n2 for n5 */6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n4 */1.4 算法和算法分析8如果解決問題P的算法A和算法B，其時間復雜度分別是TA(n)和TB(n)，則判斷A、B性能優(yōu)劣的標準是查看在n足夠大時TA(n)和TB(n)的大小關系算法效率的度量1.4 算法和算法分析9為什么采用O(f(n)而不采用f(n) ?更簡潔地表達算法的間時復雜性的“量級”。有些復雜的算法難以精確求出f(n) 。算法效率的度量算法的空間復雜

5、度S(n) = O(f(n)算法的空間需求以下二個組成部分：算法程序和輸入數據。輔助空間（工作空間），又稱額外空間。1.4 算法和算法分析10算法效率的度量對于同一算法，如果有相同的問題長度，但采用不同的輸入，其時間代價一般也不同。因此在實際的算法分析中，復雜度函數值T(n)不是唯一的設Dn為問題P的所有長度為n的實例集合，輸入實例IDn，t(I)是用來解決問題P的算法A在以I為輸入時的執(zhí)行代價（基本操作數），則算法A的最壞情形時間復雜度和最好情形時間復雜度定義如下最壞情況和最好情況1.4 算法和算法分析11算法效率的度量(教材約定) 用同一個算法處理兩個規(guī)模相同的問題，所花費的時間和空間代價

6、也不一定相同。 要全面分析一個算法，應該考慮它在最壞情況下的代價(對同樣規(guī)模的問題所花費的最大代價)、最好情況下的代價和平均情況下的代價等。 然而要全面準確地分析每個算法是相當困難的，因此本書中在分析算法的性質時將主要考慮它們在最壞情況下的代價，個別地方也涉及到其他情況。1.4 算法和算法分析12算法分析示例例: 以下為交換a和b的內容的算法，試分析其 T(n)。 temp = aa = bb = temp分析：基本運算：賦值操作。因為 執(zhí)行上述語句僅需常數時間， 所以 T(n)=O(1)。1.4 算法和算法分析13算法分析示例例: 分析以下算法的T(n)。x=0; y=0;for (k=1;

7、k=n;k+) x+;for (i=1;i=n;i+) for (j=1;j=n;j+) y+;分析：基本運算：增1操作T(n)=(n2+n)=O(n2)1.4 算法和算法分析14算法分析示例例:分析以下程序段的時間復雜度求出指定語句的頻度。i=1; while(i=n) i=i*2; 解：顯然語句的頻度是1；設語句的頻度是f(n)，則有：2f(n) n , 即f(n)log2n，取最大值f(n)=log2n 該算法的運行時間由程序中所有語句的頻度之和構成, 所以該程序段的時間復雜度為: T(n)=1+f(n)=1+ log2n= O( log2n)1.4 算法和算法分析題目求n元中的最大元M

8、AX(n)和最小元MIN(n)學習目的理解算法的評價方法體會算法設計及算法改進15MAXMIN問題算法分析示例1.4 算法和算法分析void MAXMIN1(int L, int n)int MAX = L1, j;for(int i=2;i=n;i+)if(MAXLi) MAX=Li; j=iSwap(Lj,Ln);int MIN = L1;for(int i=2;iLi)MIN=Li;16平凡算法算法討論：1.算法是正確的；2.以元素之間的比較為基本操作，則求MAX的代價是n-1，求MIN的代價是n-2，故總時間是2n-33.算法的代價只與L的長度n有關，而與L的具體元素沒有關系，故T(n

9、)=W(n)=A(n)=2n-3，亦可記為T(n)=O(n)4.空間消耗除了L之外只需幾個單元S(n)=O(1)算法思考：從n元中求最大元用n-1次比較是最優(yōu)的，從剩下的n-1元中求最小元用n-2次比較也是最優(yōu)的，但是把二者結合起來用2n-3次比較求最大元和最小元是否是最優(yōu)的呢？1.4 算法和算法分析void MAXMIN2(int L, int n)int MAX=L1, MIN=L1;for(int i=2;i=n;i+)if(MAXLi) MIN=Li;17變形算法討論：1.把MAX和MIN放在一起處理；2.算法總時間是2n-2，所以從效率上來說沒有任何改進算法思考：從算法結構可以很容易

10、的看到其不合理的地方：如果MAXLi必為假（為什么？）void MAXMIN(int L, int n)int MAX=L1, MIN=L1;for(int i=2;i=n;i+)if(MAXLi) MIN=Li;18改進一算法討論：1.算法的時間代價與L1n的內容有關： L1n 為遞增序列，需要n-1次比較， L1n 為遞減序列，需要2n-2次比較；2.顯然最好情形B(n)=n-1，最壞情形W(n)=2n-2，平均情形時間復雜度A(n)難以計算，但估計應該介于二者之間，且有A(n)L2) M1=L1;M2=L2;else M1=L2;M2=L1;elseDivide L into L1 and L2;MAXMIN(L1,n/2,M11,M21);MAXMIN(L2,n/2,M12,M22);M1=MAX(M11,M12);M2=MIN(M21,M22);19改進二算法討論：1.算法是針對n=2k設計的，同時可以擴展到n為一般正整數的情況；2.算法的時間代價與L1n的內容無關，T(n)=1.5n-2比較原來有較大改進3.基本思想是每一次比較都有助于求最大元和最小元20本章小結數據結構課程 數據結構算法程序，涉及數學、計算機硬件和軟件。數據結構定義指互相有關聯(lián)