數(shù)據(jù)結(jié)構(gòu)第一章緒論part2

1、1.3 算法的描述和分析算法的描述和分析一、算法一、算法二、算法的特性二、算法的特性三、算法設(shè)計(jì)的原則三、算法設(shè)計(jì)的原則四、算法效率的衡量方法和準(zhǔn)則四、算法效率的衡量方法和準(zhǔn)則五、算法的存儲(chǔ)空間需求五、算法的存儲(chǔ)空間需求六、算法的描述六、算法的描述七、類七、類C語言語法概要語言語法概要八、算法的評價(jià)八、算法的評價(jià)一、算法一、算法 算法（算法（Algorithm)是對特定問題求解步驟的一種描述，是對特定問題求解步驟的一種描述，它是指令的有限序列，其中，每一條指令表示一個(gè)或多個(gè)操它是指令的有限序列，其中，每一條指令表示一個(gè)或多個(gè)操作；作；例：計(jì)算例：計(jì)算 1-1/2+1/3-1/4+1/5-+1/

2、99-1/100算法算法1：自左至右逐項(xiàng)相加或相減；：自左至右逐項(xiàng)相加或相減；算法算法2：將多項(xiàng)式寫成兩個(gè)多項(xiàng)式之差：將多項(xiàng)式寫成兩個(gè)多項(xiàng)式之差： （1+1/3+1/5+1/99）-（1/2+1/4+1/6+1/100）算法算法3：先通分，再運(yùn)算；：先通分，再運(yùn)算；二、算法的特性二、算法的特性 一個(gè)算法必須滿足以下一個(gè)算法必須滿足以下五五個(gè)重要特性特性： 有窮性有窮性： 對于任意一組合法輸入值，在執(zhí)行對于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間有限時(shí)間內(nèi)完成。內(nèi)完成。 確定性確定性： 對于對于每種情況

3、每種情況下所應(yīng)執(zhí)行的操作，在算法中都有下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。在任何條件下，算法都只有一條執(zhí)行路徑。 可行性可行性 算法中的所有操作都必須算法中的所有操作都必須足夠基本足夠基本，都可以通過已，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。 有輸入有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的一作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有組變

4、量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。 有輸出有輸出 它是一組與它是一組與“輸入輸入”有確定關(guān)系的量值，是算法進(jìn)有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。能。三、算法設(shè)計(jì)的原則三、算法設(shè)計(jì)的原則通常設(shè)計(jì)一個(gè)通常設(shè)計(jì)一個(gè)“好好”的算法應(yīng)考慮達(dá)到以下目標(biāo)：的算法應(yīng)考慮達(dá)到以下目標(biāo)： 正確性正確性 可讀性可讀性 健壯性健壯性 高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求1 1正確性正確性 首先，首先，算法應(yīng)當(dāng)滿足滿足

5、以特定的“規(guī)格說明規(guī)格說明”方式給出的需求需求。 其次，其次，對算法是否“正確正確”的理解可以有以下四個(gè)層次四個(gè)層次：a a程序中不含語法錯(cuò)誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；2. . 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于易于人的理解理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3健壯性

6、健壯性 當(dāng)輸入的數(shù)據(jù)非法非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出處理出錯(cuò)的方法錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。四、算法效率的衡量方法和準(zhǔn)則四、算法效率的衡量方法和準(zhǔn)則通常有兩種兩種衡量算法效率的方法:事后統(tǒng)計(jì)法事后統(tǒng)計(jì)法事前分析估算法事前分析估算法缺點(diǎn)：缺點(diǎn)：1 1必須先運(yùn)行依據(jù)算法編制的程序；必須先運(yùn)

7、行依據(jù)算法編制的程序； 2 2所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。法本身的優(yōu)劣。和算法執(zhí)行時(shí)間時(shí)間相關(guān)的因素因素：1 1算法算法選用的策略的策略2 2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言語言4 4編譯編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量代碼的質(zhì)量5 5計(jì)算機(jī)計(jì)算機(jī)執(zhí)行指令的速度執(zhí)行指令的速度 顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行時(shí)，效率均不相同。這表明用絕計(jì)算機(jī)上

8、運(yùn)行時(shí)，效率均不相同。這表明用絕對的時(shí)間單位衡量算法的效率是不合適的。撇對的時(shí)間單位衡量算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為：認(rèn)為： 一個(gè)特定一個(gè)特定算法算法的的“運(yùn)行工作量運(yùn)行工作量”的大小，的大小，只依賴于只依賴于問題的規(guī)模問題的規(guī)模（通常用整數(shù)量（通常用整數(shù)量n表示），表示），或者說，或者說，它是問題規(guī)模的函數(shù)是問題規(guī)模的函數(shù)。 假如，隨著問題規(guī)模 n 的增長，算法算法執(zhí)行時(shí)間的增長率和執(zhí)行時(shí)間的增長率和 f(n) 的增長率相同的增長率相同，則可記作：T (n) = O(f(n)稱稱T (n) 為算法的為算法的(漸近

9、)時(shí)間復(fù)雜度時(shí)間復(fù)雜度。如何估算如何估算 算法的時(shí)間復(fù)雜度？算法的時(shí)間復(fù)雜度？ 算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （順序、分支、循環(huán)）（固有數(shù)據(jù)類型的操作）（順序、分支、循環(huán)）（固有數(shù)據(jù)類型的操作） 則算法的時(shí)間取決于兩者的綜合效果。為了便于則算法的時(shí)間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中比較同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題（或算法類型）來說是基選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。

10、算法的時(shí)間度量。算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 =原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 從算法中選取一種對于所研究的問題來說是 基本操作基本操作 的原操作，以該基本操作 在算法在算法中重復(fù)執(zhí)行的次數(shù)中重復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。語句重復(fù)執(zhí)行的次數(shù)稱為語句的頻度。頻度。 由于算法的時(shí)間復(fù)雜度考慮的只是對于問題規(guī)模n的增長率，則在難以精確計(jì)算基本操作執(zhí)行次數(shù)（或語句頻度）的情況下，只需求出它關(guān)于n的增長率或階即可。例：例： +x; O(1) 常量

11、階常量階 for (i=1;i=n;i+) +x; O(n) 線性階線性階 for (i=1;i=n;i+) for (j=1;j=n;j+) +x; O(n2) 平方階平方階 還可能呈現(xiàn)的時(shí)間復(fù)雜度有：對數(shù)階還可能呈現(xiàn)的時(shí)間復(fù)雜度有：對數(shù)階O(log n)、指數(shù)階指數(shù)階O(2n)等。等。例例一一兩兩個(gè)個(gè)矩矩陣陣相相乘乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲(chǔ)矩陣元素，以二維數(shù)組存儲(chǔ)矩陣元素，c 為為 a 和和 b 的乘積的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1;

12、 k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作時(shí)間復(fù)雜度: O(n3)例例二二選選擇擇排排序序 void select_sort(int& a, int n) / 將將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 / select_sort基本操作: 比較比較(數(shù)據(jù)元素)操作操作時(shí)間復(fù)雜度: O(n2)j = i; / 選擇第選擇第 i 個(gè)最小元素個(gè)最小元素for (k = i+1; k n; +k) if (ak aj) j = k;for ( i = 0; i1 & ch

13、ange; -i) / bubble_sort基本操作: 賦值賦值操作時(shí)間復(fù)雜度: O(n2) change = FALSE; / change 為元素進(jìn)行交換標(biāo)志為元素進(jìn)行交換標(biāo)志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡一趟起泡五、算法的存儲(chǔ)空間需求五、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為空間復(fù)雜度定義為: :其中，n為問題的規(guī)模（或大?。?。 表示隨著問題規(guī)模表示隨著問題規(guī)模 n 的增大，算法運(yùn)的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與行所需存儲(chǔ)量的增長率與 g(n) 的增長率相的增長率相同。同。S(n) = O(g(n)算法的存儲(chǔ)量

14、算法的存儲(chǔ)量包括:1輸入數(shù)據(jù)輸入數(shù)據(jù)所占空間2程序本身程序本身所占空間3輔助變量輔助變量所占空間 若若輸入數(shù)據(jù)輸入數(shù)據(jù)所占空間只取決于問題本身，所占空間只取決于問題本身，和算法無關(guān)和算法無關(guān)，則只需要分析，則只需要分析除輸入和程序之外除輸入和程序之外的輔助變量所占額外空間的輔助變量所占額外空間。 若所需額外空間相對于輸入數(shù)據(jù)量來說是若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為常數(shù)，則稱此算法為原地工作原地工作。 若所需存儲(chǔ)量依賴于特定的輸入，則通常若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。按最壞情況考慮。六、算法的描述六、算法的描述描述一個(gè)算法可以采用不同的方法，常用的有：

15、描述一個(gè)算法可以采用不同的方法，常用的有： 自然語言自然語言 流程圖及改進(jìn)的流程圖流程圖及改進(jìn)的流程圖 偽代碼偽代碼 N-S結(jié)構(gòu)流程圖結(jié)構(gòu)流程圖 PAD圖圖 本課程采用介于偽碼和本課程采用介于偽碼和C語言之間的語言之間的類類C語言語言，有時(shí)也，有時(shí)也用偽碼描述一些只含抽象操作的抽象算法；這使得數(shù)據(jù)結(jié)構(gòu)用偽碼描述一些只含抽象操作的抽象算法；這使得數(shù)據(jù)結(jié)構(gòu)和算法的描述和討論簡明清晰，不拘泥于和算法的描述和討論簡明清晰，不拘泥于C語言的細(xì)節(jié)，又語言的細(xì)節(jié)，又能容易轉(zhuǎn)換成能容易轉(zhuǎn)換成C或或C+程序。程序。七、類七、類C語言語法概要：語言語法概要： 1、預(yù)定義常量和類型：、預(yù)定義常量和類型： /函數(shù)結(jié)果

16、狀態(tài)代碼函數(shù)結(jié)果狀態(tài)代碼 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 # define INFEASIBLE -1 # define OVERFLOW -2 typedef int Status； / Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int bool; / bool是布爾類型，其值是是布爾類型，其值是TRUE或或FALSE2、數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義、數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為

17、）描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。3、基本操作的算法都用以下形式的函數(shù)描述：、基本操作的算法都用以下形式的函數(shù)描述： 函數(shù)類型函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）函數(shù)名（函數(shù)參數(shù)表） / 算法說明算法說明 語句序列語句序列 /函數(shù)名函數(shù)名 除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時(shí)對其作用給予注釋。一般而言，變量說明，必要時(shí)對其作用給予注釋。一般而言， a、b、c、d、e 等用作數(shù)據(jù)元素名；等用作數(shù)據(jù)元素名； i、j、k、l、m、n

18、等用作整形變量名；等用作整形變量名； p、q、r 等用作指針變量名。等用作指針變量名。 當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時(shí)，函數(shù)定義為當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時(shí)，函數(shù)定義為Status類型。為類型。為了便于算法描述，除了值調(diào)用方式外，增添了了便于算法描述，除了值調(diào)用方式外，增添了C+語言的引用調(diào)用的參語言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。打頭的參數(shù)即為引用參數(shù)。4、賦值語句有：、賦值語句有： 簡單賦值簡單賦值 變量名變量名 = 表達(dá)式；表達(dá)式； 串聯(lián)賦值串聯(lián)賦值 變量名變量名1 = 變量名變量名2 = = 變量名變量名k =

19、 表達(dá)式；表達(dá)式； 成組賦值成組賦值 （變量名（變量名1，變量名，變量名k）=（表達(dá)式（表達(dá)式1，表達(dá)式，表達(dá)式k）；）； 結(jié)構(gòu)名結(jié)構(gòu)名 = 結(jié)構(gòu)名；結(jié)構(gòu)名； 結(jié)構(gòu)名結(jié)構(gòu)名 =（值（值1，值，值k)； 變量名變量名 = 表達(dá)式；表達(dá)式； 變量名變量名起始下標(biāo)起始下標(biāo)終止下標(biāo)終止下標(biāo)=變量名變量名起始下標(biāo)起始下標(biāo)終止下標(biāo)終止下標(biāo)； 交換賦值交換賦值 變量名變量名變量名；變量名； 條件賦值條件賦值 變量名變量名 = 條件表達(dá)式？表達(dá)式條件表達(dá)式？表達(dá)式T：表達(dá)式：表達(dá)式F；5、選擇語句有：、選擇語句有： 條件語句條件語句1 if （表達(dá)式）語句；（表達(dá)式）語句； 條件語句條件語句2 if （表達(dá)式

20、）語句；（表達(dá)式）語句； else 語句；語句； 開關(guān)語句開關(guān)語句1 switch（表達(dá)式）（表達(dá)式） case 值值1：語句序列：語句序列1；break； case 值值n：語句序列：語句序列n；break； default：語句序列：語句序列n+1； 開關(guān)語句開關(guān)語句2 switch case 條件條件1：語句序列：語句序列1；break； case 條件條件n：語句序列：語句序列n；break； default：語句序列：語句序列n+1； 6、循環(huán)語句有：、循環(huán)語句有： for 語句語句 for（賦初值表達(dá)式序列；條件；修改表達(dá)式序列）（賦初值表達(dá)式序列；條件；修改表達(dá)式序列） 語句；語

21、句； while 語句語句 while (條件條件) 語句；語句； do-while 語句語句 do 語句序列；語句序列； while (條件）；條件）；7、結(jié)束語句有：、結(jié)束語句有： 函數(shù)結(jié)束語句函數(shù)結(jié)束語句 return 表達(dá)式；表達(dá)式； return; case結(jié)束語句結(jié)束語句 break; 異常結(jié)束語句異常結(jié)束語句 exit (異常代碼）；異常代碼）；8、輸入和輸出語句有：、輸入和輸出語句有： 輸入語句輸入語句 scanf ( 格式串格式串，變量，變量1， ，變量，變量n）；）； 輸出語句輸出語句 printf ( 格式串格式串，表達(dá)式，表達(dá)式1， ，表達(dá)式，表達(dá)式n）；）； 通常省略格式串。通常省略格式串。9、注釋、注釋 單行注釋單行注釋 /