軟件技術(shù)基礎(chǔ)

1、軟件技術(shù)基礎(chǔ)課程 18-1 主講教師：朱海華 機(jī)電學(xué)院15B426 Email: 軟件技術(shù)基礎(chǔ) 軟件技術(shù)基礎(chǔ)課程 18-2 緒緒 論論 工程軟件工程軟件概述概述 計算機(jī)三大應(yīng)用領(lǐng)域：科學(xué)計算、信息處理、過程控制科學(xué)計算、信息處理、過程控制。 隨著信息技術(shù)的普及，各類計算機(jī)軟硬件系統(tǒng)在工程應(yīng)用領(lǐng)域的廣泛應(yīng)用。 工程軟件在實際工程應(yīng)用中占有相當(dāng)重要的地位。 工程軟件主要應(yīng)用領(lǐng)域包括工程軟件主要應(yīng)用領(lǐng)域包括： 工程輔助系統(tǒng)工程輔助系統(tǒng)：工程數(shù)值計算（Engineering Computation）、計算機(jī) 輔助設(shè)計CAD、計算機(jī)輔助制造CAM、計算機(jī)輔助工程教育CAEE、計 算機(jī)集成制造系統(tǒng)CIMS

2、、計算機(jī)輔助測試CAT、工業(yè)控制IC、計算機(jī) 仿真CS等。 工程事務(wù)處理工程事務(wù)處理：分為事務(wù)型系統(tǒng)、管理型系統(tǒng)、決策型系統(tǒng)。 現(xiàn)代工程通信及信息交流現(xiàn)代工程通信及信息交流：通過支持計算機(jī)網(wǎng)絡(luò)的工程軟件不僅可以 實現(xiàn)遠(yuǎn)程的數(shù)據(jù)傳輸、狀態(tài)監(jiān)控和現(xiàn)場資源配置等工作，而且還能異地 共享和交流各種生產(chǎn)信息資源。 軟件技術(shù)基礎(chǔ)課程 18-3 緒緒 論論 工程軟件工程軟件的基本元素的基本元素 工程軟件的三個基本要素是數(shù)據(jù)數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和算法算法。 工程數(shù)據(jù)工程數(shù)據(jù)是工程軟件系統(tǒng)的處理對象。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是對工程數(shù)據(jù)的組織。組織結(jié)構(gòu)良好的數(shù)據(jù)不僅可以提高工程數(shù) 據(jù)處理的效率，而且數(shù)據(jù)的可靠性也能

3、得到有效的保障。 算法算法提供處理數(shù)據(jù)的手段和方法，是提取數(shù)據(jù)內(nèi)涵的一系列行為的總稱。 軟件技術(shù)基礎(chǔ)課程 18-4 緒緒 論論 著名計算機(jī)科學(xué)家著名計算機(jī)科學(xué)家Wirth(Wirth(沃思沃思) )提出提出: : 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +算法程序算法程序 然而然而, , 僅有這些還不夠僅有這些還不夠, , 應(yīng)是應(yīng)是: : 數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具和環(huán)境程序數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具和環(huán)境程序 程序設(shè)計程序設(shè)計 算法設(shè)計算法設(shè)計 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 行為特性的行為特性的 設(shè)計設(shè)計 結(jié)構(gòu)特性的結(jié)構(gòu)特性的 設(shè)計設(shè)計 程序中的指令必須是機(jī)器可執(zhí)行的，算法中的指令則無此限制。程序中的指令必須是

4、機(jī)器可執(zhí)行的，算法中的指令則無此限制。 算法的效率通常與數(shù)據(jù)的存儲結(jié)構(gòu)有直接關(guān)系。算法的效率通常與數(shù)據(jù)的存儲結(jié)構(gòu)有直接關(guān)系。 軟件技術(shù)基礎(chǔ)課程 18-5 軟件技術(shù)基礎(chǔ)課程 18-6 1.1 算法的基本概念算法的基本概念 n概念概念 算法是為解決一個問題采取的方法和步驟算法是為解決一個問題采取的方法和步驟。也就也就 是說，算法是為實現(xiàn)某種計算過程而規(guī)定的基本是說，算法是為實現(xiàn)某種計算過程而規(guī)定的基本 動作的執(zhí)行序列。動作的執(zhí)行序列。 n算法的實現(xiàn)算法的實現(xiàn) 自動機(jī)器解自動機(jī)器解-指令的有限序列指令的有限序列。 n自動機(jī)的能力自動機(jī)的能力：對于執(zhí)行體系來說是：對于執(zhí)行體系來說是一種制約一種制約 n

5、描述形式的描述形式的理解能力理解能力 n實現(xiàn)描述的實現(xiàn)描述的執(zhí)行能力執(zhí)行能力 n算法的算法的有限自動機(jī)解有限自動機(jī)解-在有限的存儲在有限的存儲空間空間和有限和有限 的的時間時間內(nèi)通過有限的內(nèi)通過有限的步驟步驟得到預(yù)期的得到預(yù)期的結(jié)果結(jié)果。 軟件技術(shù)基礎(chǔ)課程 18-7 1.1.1 算法的基本特征算法的基本特征 n1. 能行性能行性(effectiveness): n每一操作都可以通過可實現(xiàn)的基本運算執(zhí)行有限次來每一操作都可以通過可實現(xiàn)的基本運算執(zhí)行有限次來 實現(xiàn)實現(xiàn) n步驟合理性步驟合理性 n步驟可操作性步驟可操作性 n達(dá)到預(yù)期目的達(dá)到預(yù)期目的 n與具體實現(xiàn)方式和環(huán)境有關(guān)。與具體實現(xiàn)方式和環(huán)境有

6、關(guān)。 n2. 確定性確定性(definiteness): n在所指定的在所指定的范疇范疇內(nèi)內(nèi)無模糊性無模糊性 n在所指定的在所指定的范疇范疇內(nèi)內(nèi)無多義性無多義性。 檢驗檢驗：相同輸入：相同輸入 相同輸出。相同輸出。 軟件技術(shù)基礎(chǔ)課程 18-8 算法的基本特征算法的基本特征（續(xù)續(xù)） n3. 有窮性有窮性(finiteness) n步驟有窮性步驟有窮性 n時間有限性時間有限性 n4. 完備性完備性(self-contained) n初始條件應(yīng)明確初始條件應(yīng)明確 n限定范圍內(nèi)條件應(yīng)齊備限定范圍內(nèi)條件應(yīng)齊備 n結(jié)果可展現(xiàn)結(jié)果可展現(xiàn) n對異常情況的容錯性對異常情況的容錯性 軟件技術(shù)基礎(chǔ)課程 18-9 算

7、法的定義算法的定義 一組嚴(yán)謹(jǐn)定義運算一組嚴(yán)謹(jǐn)定義運算順序順序的的規(guī)則規(guī)則，并，并 且每一個規(guī)則都是且每一個規(guī)則都是有效有效且且明確明確的，此的，此 順序?qū)⒃陧樞驅(qū)⒃谟邢抻邢薜拇螖?shù)下的次數(shù)下終止終止并獲得預(yù)并獲得預(yù) 期的期的結(jié)果結(jié)果。 軟件技術(shù)基礎(chǔ)課程 18-10 1.1.2 算法的基本要素算法的基本要素 n對對數(shù)據(jù)對象的運算和操作數(shù)據(jù)對象的運算和操作 n針對算法涉及的數(shù)據(jù)信息針對算法涉及的數(shù)據(jù)信息 n最基本的動作和步驟單元最基本的動作和步驟單元 n算法的控制結(jié)構(gòu)算法的控制結(jié)構(gòu) n針對算法的過程步驟針對算法的過程步驟 n控制基本操作和步驟的組合順序控制基本操作和步驟的組合順序 軟件技術(shù)基礎(chǔ)課程

8、18-11 算法要素描述系統(tǒng)的組成算法要素描述系統(tǒng)的組成 n1. 運算和操作的描述運算和操作的描述 n標(biāo)識符標(biāo)識符：用戶編程時使用的名字：用戶編程時使用的名字 n運算符運算符: n算術(shù)運算算術(shù)運算符符：+，-，*，/ 等等 n關(guān)系運算符：關(guān)系運算符：，=， !=，=，= n邏輯邏輯運算符運算符： r=m%n; while(r!=0) m=n; n=r; r=m%n; return n; 軟件技術(shù)基礎(chǔ)課程 18-14 算法要素描述系統(tǒng)的組成算法要素描述系統(tǒng)的組成 n2. 控制結(jié)構(gòu)控制結(jié)構(gòu)控制基本運算的控制基本運算的執(zhí)行順序執(zhí)行順序 n賦值賦值 n選擇選擇-條件轉(zhuǎn)移條件轉(zhuǎn)移 (多分枝選擇多分枝選擇

9、) n循環(huán)語句循環(huán)語句 以上三種動作語句的組合可以完成任何復(fù)雜的過程序列以上三種動作語句的組合可以完成任何復(fù)雜的過程序列 軟件技術(shù)基礎(chǔ)課程 18-15 賦值賦值語句語句 n賦值語句的形式為賦值語句的形式為 a= =e; ，其中其中a為變量名或數(shù)組為變量名或數(shù)組 元素，元素，e為算術(shù)表達(dá)式或邏輯表達(dá)式。為算術(shù)表達(dá)式或邏輯表達(dá)式。 n如果如果a和和b都都為為變量名或數(shù)組元素，則可用記號變量名或數(shù)組元素，則可用記號 ab，表示將表示將a與與b的內(nèi)容進(jìn)行交換。的內(nèi)容進(jìn)行交換。(或或 c=a;a=b;b=c;) 軟件技術(shù)基礎(chǔ)課程 18-16 控制轉(zhuǎn)移控制轉(zhuǎn)移語句語句 n無條件轉(zhuǎn)移語句用如下形式：無條件轉(zhuǎn)

10、移語句用如下形式： goto 標(biāo)號標(biāo)號 n條件轉(zhuǎn)移語句有以下兩種形式：條件轉(zhuǎn)移語句有以下兩種形式： IF ( C ) S 或或 IF ( C) S1 ELSE S2 軟件技術(shù)基礎(chǔ)課程 18-17 循環(huán)循環(huán)語句語句 nWHILE語句的形式為：語句的形式為： while() ; do while(); nFOR語句的形式為語句的形式為: for (i=1;i=end;i+) ; 軟件技術(shù)基礎(chǔ)課程 18-18 其他輔助語句：其他輔助語句： lbreak; 終止整個循環(huán)終止整個循環(huán) lcontinue；退出本次循環(huán)退出本次循環(huán) lreturn()語句用于結(jié)束算法的執(zhí)行語句用于結(jié)束算法的執(zhí)行 lREAD

11、（或（或INPUT）語句用于輸入）語句用于輸入 lOUTPUT（或（或PRINT，或，或WRITE）語句用于輸出。）語句用于輸出。 軟件技術(shù)基礎(chǔ)課程 18-19 1.2 計算機(jī)算法設(shè)計的基本方法計算機(jī)算法設(shè)計的基本方法 n1. 列舉法列舉法 (枚舉法枚舉法) 首先依據(jù)問題的部分條件首先依據(jù)問題的部分條件確定確定答案的大致答案的大致范圍范圍，然后在，然后在 此范圍內(nèi)對所有可能的此范圍內(nèi)對所有可能的情況情況逐一逐一驗證驗證，直到全部情況，直到全部情況 驗證完。若某個情況使驗證驗證完。若某個情況使驗證符合符合問題的條件，則為本問題的條件，則為本 題的一個題的一個答案答案；若全部情況驗證完后均不符合題

12、目的；若全部情況驗證完后均不符合題目的 條件，則問題條件，則問題無解無解 n確定枚舉的確定枚舉的集合集合(范圍）范圍） n確定枚舉的確定枚舉的條件條件和和驗證驗證方法（起止，順序，相關(guān)性，方法（起止，順序，相關(guān)性， 過程）過程） n優(yōu)化枚舉的條件和范圍。優(yōu)化枚舉的條件和范圍。 n優(yōu)點：簡單。優(yōu)點：簡單。 n弱點：低效弱點：低效 軟件技術(shù)基礎(chǔ)課程 18-20 列舉法實例列舉法實例 n求不定方程的百雞問題：求不定方程的百雞問題： 設(shè)設(shè)x ，y，z分別為母雞、公雞和小雞的只數(shù)。母雞每只三元、公分別為母雞、公雞和小雞的只數(shù)。母雞每只三元、公 雞每只二元、小雞兩只一元。問百元買百雞有幾種解法？雞每只二元

13、、小雞兩只一元。問百元買百雞有幾種解法？ 寫代數(shù)方程：寫代數(shù)方程： x+y+ z=100 3x+2y+z/2=100 軟件技術(shù)基礎(chǔ)課程 18-21 用列舉法寫算法就十分方便：用列舉法寫算法就十分方便： void BuyChicks() int x,y,z; for ( x=0, x=100, x+) for( y=0, y=100, y+) for( z=0, z=100, z+) m = x+y+z; n=3*x+2*y+0.5*z; if (m=100) ; 如何優(yōu)化如何優(yōu)化? 軟件技術(shù)基礎(chǔ)課程 18-22 優(yōu)化后的程序：優(yōu)化后的程序： void BuyChicks() int x,y,z

14、; for ( x=0; x=33; x+) /最多可以買最多可以買33只母雞只母雞 for( y=0; y=50-1.5*x; y+) /最多可買最多可買50只公雞只公雞 z = 100-x-y; if (3*x + 2*y + 0.5*z) =100) cout 過程的遞歸過程的遞歸 n需要需要機(jī)器能力機(jī)器能力的支持的支持 n效率問題效率問題 軟件技術(shù)基礎(chǔ)課程 18-25 n直接遞歸直接遞歸: 遞歸函數(shù)的函數(shù)體中存在顯式的自我調(diào)用時，被稱為直接遞歸。例如，函遞歸函數(shù)的函數(shù)體中存在顯式的自我調(diào)用時，被稱為直接遞歸。例如，函 數(shù)數(shù)foo中包含自我調(diào)用，因此是直接遞歸。中包含自我調(diào)用，因此是直接

15、遞歸。 int foo(int x) if (x = 0) return x; return foo(x - 1); n間接遞歸間接遞歸： 如果如果函數(shù)中函數(shù)中包含對另一個函數(shù)的調(diào)用而該函數(shù)最終會調(diào)用函數(shù)包含對另一個函數(shù)的調(diào)用而該函數(shù)最終會調(diào)用函數(shù)foo，則被，則被 稱為間接遞歸稱為間接遞歸。 int foo(int x) if (x = 0) return x; return bar(x); int bar(int y) return foo(y - 1); 軟件技術(shù)基礎(chǔ)課程 18-26 遞歸設(shè)計方法遞歸設(shè)計方法 n把把階數(shù)階數(shù)較高的一個過程，轉(zhuǎn)化為階數(shù)較低較高的一個過程，轉(zhuǎn)化為階數(shù)較低同類

16、型同類型 的過程。的過程。 n采用遞歸編寫程序能使程序變得非常采用遞歸編寫程序能使程序變得非常簡單簡單而而清晰清晰。 遞歸的主要思想包括三個方面：遞歸的主要思想包括三個方面： na) 定義形式是遞歸的。定義形式是遞歸的。 nb) 數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。 nc) 問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比用問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比用 迭代求解更簡單。迭代求解更簡單。 軟件技術(shù)基礎(chǔ)課程 18-27 遞歸設(shè)計舉例遞歸設(shè)計舉例 n對于輸入的參數(shù)對于輸入的參數(shù)n，依次打印出自然數(shù)，依次打印出自然數(shù)1至至n。 非遞歸解：非遞歸解：

17、 #include Using namespace std; void write(int n) int k; for (k=1; k=n; k+) coutkendl; return; 遞歸解：遞歸解： #include Using namespace std; void write1(int n) if ( n!=0 )/邊界條件，遞歸入口邊界條件，遞歸入口 write1( n-1 )； /遞歸前進(jìn)段遞歸前進(jìn)段 coutn1)穿孔圓盤，盤的尺寸由下到上依次變小。要求 按下列規(guī)則將所有圓盤移至C桿：每次只能移動一個圓盤；大盤不能疊在小盤上面。 軟件技術(shù)基礎(chǔ)課程 18-31 n算法描述：算法描

18、述： Hanoi(n,X,Y,Z) if n=1 then move (X,1,Z) else Hanoi (n-1, X, Z, Y) move (X, n, Z) Hanoi(n-1, Y, X, Z) endif return 前進(jìn)段前進(jìn)段? 返回段返回段? 邊界條件邊界條件? 軟件技術(shù)基礎(chǔ)課程 18-32 n回溯法回溯法 n試探法試探法 n無法總結(jié)出求解規(guī)律。無法總結(jié)出求解規(guī)律。 n無法列舉可能的條件和解集。無法列舉可能的條件和解集。 n逐步試探逐步試探 n局部成功，則繼續(xù)試探。局部成功，則繼續(xù)試探。 n若失敗，沿原路退回若干步，改變條件和方向再試，直至若失敗，沿原路退回若干步，改變條

19、件和方向再試，直至 找到解。找到解。 軟件技術(shù)基礎(chǔ)課程 18-33 皇后問題皇后問題 N N皇后問題自然語言描述：皇后問題自然語言描述： 在在n n行行n n列的國際象棋棋盤上，列的國際象棋棋盤上， 若兩個皇后位于同一行、同若兩個皇后位于同一行、同 一列、同一對角線上，則稱一列、同一對角線上，則稱 為它們?yōu)榛ハ喙簟樗鼈優(yōu)榛ハ喙簟?n n皇后問題的皇后問題的解解是指：是指： 找到這找到這n n個皇后的互不攻個皇后的互不攻 擊的擊的布局布局 思考思考：1）如何表示棋盤、棋子和布棋？）如何表示棋盤、棋子和布棋？ 2）如何描述布棋規(guī)則？）如何描述布棋規(guī)則？ 3）如何設(shè)計布棋步驟？）如何設(shè)計布棋步

20、驟？ 軟件技術(shù)基礎(chǔ)課程 18-34 n基本思路基本思路 依次為每一行確定該行皇后的合法位置依次為每一行確定該行皇后的合法位置 n安放安放第第i i行行皇后時，需要在列的方向從皇后時，需要在列的方向從0 0到到n-1n-1試探試探( (j = 0, j = 0, , , n-1)n-1) n在在第第j j列列安放一個皇后安放一個皇后 n如果在如果在列、主對角線、次對角線列、主對角線、次對角線方向有其它皇后，方向有其它皇后， 則出現(xiàn)攻擊，撤消在則出現(xiàn)攻擊，撤消在第第j j列列安放的皇后：安放的皇后： n如果沒有出現(xiàn)攻擊，在如果沒有出現(xiàn)攻擊，在第第j j列列安放的皇后不動安放的皇后不動 遞歸安放遞歸

21、安放第第i+1i+1行行皇后皇后 n如果如果第第i i行行不能安放皇后，則不能安放皇后，則回溯回溯到到第第i-1i-1行行，撤銷該行的皇后，撤銷該行的皇后， 并從其所在的下一個列并從其所在的下一個列( (j+1j+1) )繼續(xù)試探。繼續(xù)試探。 程序?qū)崿F(xiàn)的要素？程序?qū)崿F(xiàn)的要素？ 軟件技術(shù)基礎(chǔ)課程 18-35 皇后問題皇后問題 對于皇后問題來說，由于每 一行、每一列和每一個對角 線，都只能放一個皇后，當(dāng) 一個皇后放到棋盤上后，不 管它放在棋盤的什么位置， 它所影響的行和列方向上的 棋盤位置是固定的，因此在 行、列方面沒有什么信息可 以利用。但在不同的位置， 在對角線方向所影響的棋盤 位置數(shù)則是不同

22、的?？梢韵?象，如果把一個皇后放在棋 盤的某個位置后，它所影響 的棋盤位置數(shù)少，那么給以 后放皇后留下的余地就太大， 找到解的可能性也大；反之 留有余地就小，找到解的可 能性也小。 軟件技術(shù)基礎(chǔ)課程 18-36 思考題思考題 解的唯一性解的唯一性? 1 12 23 3n n 1 2 i n 解的完備性解的完備性 -全部解集全部解集? 無解的證明無解的證明? 軟件技術(shù)基礎(chǔ)課程 18-37 軟件技術(shù)基礎(chǔ)課程 18-38 1.3 算法的復(fù)雜度分析算法的復(fù)雜度分析 n算法的評價算法的評價 n算法的復(fù)雜度算法的復(fù)雜度 n算法的最優(yōu)性算法的最優(yōu)性 n快速算法的設(shè)計快速算法的設(shè)計 n制約算法效率的要素制約算

23、法效率的要素 n時間時間 n空間空間 軟件技術(shù)基礎(chǔ)課程 18-39 算法評價標(biāo)準(zhǔn)算法評價標(biāo)準(zhǔn) n算法評價標(biāo)準(zhǔn)算法評價標(biāo)準(zhǔn) n正確性正確性 n程序不含語法錯誤程序不含語法錯誤 n對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果 n對于精心挑選的典型、苛刻的幾組輸入數(shù)據(jù)能夠得出滿足要求對于精心挑選的典型、苛刻的幾組輸入數(shù)據(jù)能夠得出滿足要求 的結(jié)果的結(jié)果-一般作為衡量標(biāo)準(zhǔn)一般作為衡量標(biāo)準(zhǔn) n對于一切合法的輸入數(shù)據(jù)對于一切合法的輸入數(shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果 - - 很難滿足很難滿足(無法枚舉無法枚舉) n可讀性可讀性: 容易閱讀理解，

24、模塊化，可以犧牲效率容易閱讀理解，模塊化，可以犧牲效率 n健壯性健壯性：異常處理機(jī)制：異常處理機(jī)制 n高效率高效率與與低存儲量低存儲量需求需求 軟件技術(shù)基礎(chǔ)課程 18-40 1.3.1 算法的時間復(fù)雜度算法的時間復(fù)雜度 n1. 時間復(fù)雜度時間復(fù)雜度 - 一個算法運行時間的相對度量。一 個程序的時間復(fù)雜度是指程序從開始到結(jié)束運行所需要 的時間。 n算法執(zhí)行時間算法執(zhí)行時間: n算法算法執(zhí)行時間執(zhí)行時間= =原操作的執(zhí)行次數(shù)之和原操作的執(zhí)行次數(shù)之和* *原操作的執(zhí)行時間原操作的執(zhí)行時間 n算法執(zhí)行所需考慮因素算法執(zhí)行所需考慮因素: n與非關(guān)鍵性細(xì)節(jié)無關(guān)與非關(guān)鍵性細(xì)節(jié)無關(guān) n與執(zhí)行算法的機(jī)器速度無關(guān)

25、與執(zhí)行算法的機(jī)器速度無關(guān) n與輔助環(huán)境無關(guān)與輔助環(huán)境無關(guān) n時間復(fù)雜度時間復(fù)雜度度量方法度量方法: 算法基本操作算法基本操作重復(fù)執(zhí)行的次數(shù)重復(fù)執(zhí)行的次數(shù) 是模塊是模塊n的某一個函數(shù)的某一個函數(shù)f(n)。 工作量工作量 = f(n) n：問題的規(guī)模：問題的規(guī)模 n時間復(fù)雜度表示方法時間復(fù)雜度表示方法： T(n) = O(f(n) 軟件技術(shù)基礎(chǔ)課程 18-41 n隨著模塊n的增大，算法執(zhí)行時間的增長率和f(n)增長率成 正比。 n在計算時間復(fù)雜度時，先找出算法的基本操作先找出算法的基本操作，然后根據(jù) 對應(yīng)的各語句確定它的執(zhí)行次數(shù)確定它的執(zhí)行次數(shù)，再找出T(n)的同數(shù)量級 （它的同數(shù)量級有以下：1，

26、log(2)n，n，n log(2)n ，n的 平方，n的三次方，2的n次方，n!），找出后，令f(n) = 該數(shù)量級，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時間復(fù) 雜度T(n) = O(f(n) 時間復(fù)雜度分析時間復(fù)雜度分析 軟件技術(shù)基礎(chǔ)課程 18-42 乘法運算是乘法運算是基本操作基本操作，因為：，因為： 核心操作，處于最深層循環(huán)；核心操作，處于最深層循環(huán)； 花費時間（相對于加法）?；ㄙM時間（相對于加法）。 例例 n 階矩階矩 陣相乘的算法陣相乘的算法 for ( i = 1; i=n; +i ) for (j = 1; j=n; +j ) c i j = 0 ; for (k

27、= 1; k= n; +k ) c i j += a i k * b k j 乘法、加法執(zhí)乘法、加法執(zhí) 行次數(shù)均為行次數(shù)均為 n3 時間復(fù)雜度分析舉例時間復(fù)雜度分析舉例 軟件技術(shù)基礎(chǔ)課程 18-43 按數(shù)量級遞增排列，常見的時間復(fù)雜度有：按數(shù)量級遞增排列，常見的時間復(fù)雜度有： 常量階：常量階：O(1) 對數(shù)階：對數(shù)階：O(logn) 線性階：線性階：O(n) 線性對數(shù)階：線性對數(shù)階： O(nlog n) 平方階：平方階：O( n2 ) 立方階：立方階：O( n3 ) K次方階：次方階：O( nk ) 指數(shù)階：指數(shù)階：O( 2n ) T(n)=O(f(n) 時間復(fù)雜度的表示時間復(fù)雜度的表示 基本

28、操作執(zhí)行次數(shù)為基本操作執(zhí)行次數(shù)為n n3 3，與整個運行時間成正比因此以，與整個運行時間成正比因此以n n 的函數(shù)作為效率衡量標(biāo)準(zhǔn)。記作：的函數(shù)作為效率衡量標(biāo)準(zhǔn)。記作： T(n)=O(n3 ) 一般而言，基本操作重復(fù)執(zhí)行的一般而言，基本操作重復(fù)執(zhí)行的次數(shù)次數(shù)是問題規(guī)模是問題規(guī)模n n的函數(shù)的函數(shù) T(n)T(n)，當(dāng)，當(dāng)n n趨于無窮大時，趨于無窮大時，T(n)T(n)的數(shù)量級（價）稱為算法的數(shù)量級（價）稱為算法 的漸近時間復(fù)雜度，記作：的漸近時間復(fù)雜度，記作： 軟件技術(shù)基礎(chǔ)課程 18-44 算法的最優(yōu)性算法的最優(yōu)性 n最優(yōu)性定義最優(yōu)性定義: n執(zhí)行的基本運算執(zhí)行的基本運算相對相對最少。最少。

29、 n尋優(yōu)過程尋優(yōu)過程 n設(shè)計算法設(shè)計算法A，確定響應(yīng)的上界，確定響應(yīng)的上界W(n) 最壞最壞 n改進(jìn)算法改進(jìn)算法, 確定響應(yīng)的下界確定響應(yīng)的下界F(n) 至少至少 n若若W(n)= F(n), 則已獲得最優(yōu)算法則已獲得最優(yōu)算法, 否則繼續(xù)改進(jìn)否則繼續(xù)改進(jìn). n即即F(n)同時具備必要性和充分性同時具備必要性和充分性, 則算法為最優(yōu)則算法為最優(yōu). n快速算法快速算法 n時間復(fù)雜度最小時間復(fù)雜度最小 軟件技術(shù)基礎(chǔ)課程 18-45 1.3.2 算法的空間復(fù)雜度算法的空間復(fù)雜度 n空間復(fù)雜度：空間復(fù)雜度：是指程序運行從開始到結(jié)束所需的存儲空間。 n執(zhí)行算法所需要的執(zhí)行算法所需要的存儲存儲空間空間包括包

30、括： n算法算法程序程序所占所占空間空間 n輸入數(shù)據(jù)輸入數(shù)據(jù)所占所占空間空間 n執(zhí)行過程所需的執(zhí)行過程所需的額外額外空間空間 通常以算法的空間復(fù)雜度作為算法所需存儲空間的量度。 空間復(fù)雜度的表示：空間復(fù)雜度的表示： S(n)=O(g(n) 空間復(fù)雜度也是問題規(guī)模n的函數(shù)。表示隨問題規(guī)模n 的增大，算法運行所需存儲量的增長率與g(n)的增長率相 同。 軟件技術(shù)基礎(chǔ)課程 18-46 算法分析舉例算法分析舉例 n求和的例子，求和的例子， int n= 100; int sum = 0; for (int i=1;i物理上相鄰物理上相鄰, 關(guān)系自然確定關(guān)系自然確定 n易于易于描述線性結(jié)構(gòu)描述線性結(jié)構(gòu)，

31、也可，也可存儲經(jīng)過線性化處理的非線性結(jié)存儲經(jīng)過線性化處理的非線性結(jié) 構(gòu)構(gòu) n主要數(shù)據(jù)類型主要數(shù)據(jù)類型: 向量（表格存儲結(jié)構(gòu)）向量（表格存儲結(jié)構(gòu)）, 數(shù)組數(shù)組 n高級計算機(jī)語言以高級計算機(jī)語言以數(shù)據(jù)類型數(shù)據(jù)類型的方式提供了一個基本數(shù)據(jù)結(jié)的方式提供了一個基本數(shù)據(jù)結(jié) 構(gòu)集的存儲和操作。構(gòu)集的存儲和操作。 n影響選擇的因素：數(shù)據(jù)的影響選擇的因素：數(shù)據(jù)的訪問效率訪問效率和存儲和存儲空間占用空間占用的權(quán)衡。的權(quán)衡。 軟件技術(shù)基礎(chǔ)課程 18-66 軟件技術(shù)基礎(chǔ)課程 18-67 n順序結(jié)構(gòu)數(shù)據(jù)的存取順序結(jié)構(gòu)數(shù)據(jù)的存取 軟件技術(shù)基礎(chǔ)課程 18-68 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)分析分析 線性結(jié)構(gòu)線性結(jié)構(gòu) B B（D

32、 D，R R） D Daa，b b，c c，d d，e e，ff R R(b(b，c)c),(c(c，d),(dd),(d，a),(aa),(a，f),f),（f f，e e） 順序存儲的示意圖（假順序存儲的示意圖（假 設(shè)每一個數(shù)據(jù)元素占一設(shè)每一個數(shù)據(jù)元素占一 個存儲單元），數(shù)據(jù)元個存儲單元），數(shù)據(jù)元 素的存儲空間是連續(xù)的。素的存儲空間是連續(xù)的。 軟件技術(shù)基礎(chǔ)課程 18-69 n 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) n每個節(jié)點由兩部分組成每個節(jié)點由兩部分組成: 數(shù)據(jù)域數(shù)據(jù)域, 位置指示域位置指示域(指針域指針域) n即可實現(xiàn)線性結(jié)構(gòu)即可實現(xiàn)線性結(jié)構(gòu), 又可表示非線性結(jié)構(gòu)又可表示非線性結(jié)構(gòu) n特點特

33、點: n可以表示可以表示任意復(fù)雜任意復(fù)雜的結(jié)構(gòu)的結(jié)構(gòu) n存儲空間存儲空間不連續(xù)不連續(xù) n存儲順序與結(jié)構(gòu)存儲順序與結(jié)構(gòu)順序不一致順序不一致 n不能隨機(jī)訪問不能隨機(jī)訪問 n訪問訪問效率不均等效率不均等 n主要形式主要形式: 單鏈表、雙鏈表、多重鏈表、循環(huán)鏈表單鏈表、雙鏈表、多重鏈表、循環(huán)鏈表 data 單元節(jié)點 P 軟件技術(shù)基礎(chǔ)課程 18-70 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯κ纠纠?每個結(jié)點設(shè)一指針，用以指出每個結(jié)點設(shè)一指針，用以指出 其后件的存儲序號。最后一個其后件的存儲序號。最后一個 結(jié)點的指針為空，用結(jié)點的指針為空，用“0”0”表表 示。示。第一個結(jié)點專門用一個指第一個結(jié)點專門用一個指 針（稱為頭指針，

34、用針（稱為頭指針，用HEADHEAD表示）表示） 指向它。指向它。 線性結(jié)構(gòu)線性結(jié)構(gòu) B B（D D，R R） D Daa，b b，c c，d d，e e，ff R R(b(b，c)c),(c(c，d),(dd),(d， a),(aa),(a，f),f),（f f，e e） data 單元節(jié)點單元節(jié)點 P HEAD指針?biāo)复鎯Φ刂肥牵?軟件技術(shù)基礎(chǔ)課程 18-71 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系 1.1.數(shù)據(jù)的邏輯結(jié)構(gòu)必定要有某種存儲結(jié)構(gòu)實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)必定要有某種存儲結(jié)構(gòu)實現(xiàn) 2.2.兩種結(jié)構(gòu)的關(guān)聯(lián)既不固定，也不唯一。兩種結(jié)構(gòu)的關(guān)聯(lián)既不固定，也不唯一。 3.3

35、.常用數(shù)據(jù)結(jié)構(gòu)的分類可以常用數(shù)據(jù)結(jié)構(gòu)的分類可以定義在邏輯結(jié)構(gòu)上定義在邏輯結(jié)構(gòu)上， 也可以也可以定義在存儲結(jié)構(gòu)上定義在存儲結(jié)構(gòu)上，還可以，還可以定義在存儲定義在存儲 方法上。方法上。 軟件技術(shù)基礎(chǔ)課程 18-72 2.1.3 數(shù)據(jù)結(jié)構(gòu)的圖形表示 n邏輯結(jié)構(gòu)的表示邏輯結(jié)構(gòu)的表示 n符號的表示符號的表示 B = ( D, R) B - 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu), D - 數(shù)據(jù)元素的集合數(shù)據(jù)元素的集合, R - D上的一個關(guān)系上的一個關(guān)系 n圖形的表示圖形的表示 d2d3d1d4 d5 根節(jié)點根節(jié)點 內(nèi)部節(jié)點內(nèi)部節(jié)點 終節(jié)點終節(jié)點 關(guān)系描述關(guān)系描述 軟件技術(shù)基礎(chǔ)課程 18-73 例、家族的族譜例、家族的族譜

36、家族的族譜反映的是家族成員之間的血緣關(guān)系，假設(shè)家族的族譜反映的是家族成員之間的血緣關(guān)系，假設(shè) 某家族有某家族有1010個成員：個成員：A A、B B、C C、D D、E E、F F、G G、H H、I I、J J，他，他 們之間的血緣關(guān)系可以用如下圖表示。們之間的血緣關(guān)系可以用如下圖表示。 這種分支結(jié)構(gòu)關(guān)系被稱為樹結(jié)構(gòu)，它很象一棵倒置的這種分支結(jié)構(gòu)關(guān)系被稱為樹結(jié)構(gòu)，它很象一棵倒置的 樹，樹，A A 是樹的根。是樹的根。 非線性結(jié)構(gòu)的圖形表示 J J I I A A C C H HG GF FE E 家族樹的圖示表示家族樹的圖示表示 血緣關(guān)系是血緣關(guān)系是 一種非線性結(jié)構(gòu)關(guān)系一種非線性結(jié)構(gòu)關(guān)系 B

37、 BD D 軟件技術(shù)基礎(chǔ)課程 18-74 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究對象及的研究對象及本課程討論的問題本課程討論的問題 數(shù)據(jù)結(jié)構(gòu)的研究對象：數(shù)據(jù)結(jié)構(gòu)的研究對象： n非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，不一定能在分非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，不一定能在分 析數(shù)學(xué)范疇內(nèi)建立解析模型析數(shù)學(xué)范疇內(nèi)建立解析模型 n運算操作以插入、刪除、查找、更改為主。運算操作以插入、刪除、查找、更改為主。 本課程討論的問題本課程討論的問題： 應(yīng)用中常用的幾種數(shù)據(jù)結(jié)構(gòu)，以及如何存應(yīng)用中常用的幾種數(shù)據(jù)結(jié)構(gòu)，以及如何存 儲儲, , 如何處理它們。如何處理它們。 軟件技術(shù)基礎(chǔ)課程 18-75 操作與數(shù)據(jù)結(jié)構(gòu)的定義密切相關(guān)。主要算法涉及到以下操作：操作與數(shù)據(jù)結(jié)構(gòu)的定義密切相關(guān)。主要算法涉及到以下操作： 插入插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置插入新的數(shù)據(jù)元素。：在數(shù)據(jù)結(jié)構(gòu)中的指定位置插入新的數(shù)據(jù)元素。 刪除刪除：刪去數(shù)據(jù)結(jié)構(gòu)中的指定的數(shù)據(jù)元素。：刪去數(shù)據(jù)結(jié)構(gòu)中的指定的數(shù)據(jù)