OA自動化理工大學(xué)指揮自動化學(xué)院

OA自動化理工大學(xué)指揮自動化學(xué)院編寫陳衛(wèi)衛(wèi)（2008.2）審批理工大學(xué)指揮自動化學(xué)院課程教案教員姓名：陳衛(wèi)衛(wèi)單位：軟件技術(shù)教研室課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)總學(xué)時：60+20適用對象：生長干部非合訓(xùn)本科學(xué)員授課學(xué)期：2008年春季學(xué)期理工大學(xué)訓(xùn)練部制表課程簡介一、課程定位《算法與數(shù)據(jù)結(jié)構(gòu)》是仿真工程（非合訓(xùn)）、網(wǎng)絡(luò)工程（合一門重要的核心課程。通過本課程的教學(xué)，使學(xué)員知道數(shù)據(jù)結(jié)構(gòu)的一般原理，掌握表、算法設(shè)計(jì)方法，以及對算法效率的評估方法，知道什么是好的算法，如何設(shè)計(jì)和選擇好的算法，為學(xué)習(xí)后續(xù)的《操作系統(tǒng)》、《編譯原理》、《軟件工程》等專業(yè)課程，設(shè)計(jì)系統(tǒng)程序打下基礎(chǔ)。本課程的先修課程為：《計(jì)算機(jī)程序設(shè)計(jì)導(dǎo)論》（C語言）、《離散數(shù)學(xué)》。二、課程內(nèi)涵（一）總體目標(biāo)通過本課程的教學(xué)，使學(xué)員懂得數(shù)據(jù)結(jié)構(gòu)的一般原理，掌握表、各運(yùn)算的算法，學(xué)會對算法的評估方法。培養(yǎng)學(xué)員的算法設(shè)計(jì)能力、下堅(jiān)實(shí)的理論基礎(chǔ)。（二）主要內(nèi)容——表結(jié)用軟件方法處理問題的能力。（三）對學(xué)員的要求能夠熟練地使用C語言。三、教學(xué)設(shè)計(jì)《算法和數(shù)據(jù)結(jié)構(gòu)》是一門理論性與實(shí)踐性都很強(qiáng)的重要核心解。法，最后考慮如何編程實(shí)現(xiàn)，讓學(xué)生體驗(yàn)解決問題的一般過程。用詞，培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)作風(fēng)。立設(shè)計(jì)“好”算法的意識。具體內(nèi)容如下：1．圍繞表、樹、圖三大基本結(jié)構(gòu)選擇授課內(nèi)容，依照“邏輯結(jié)構(gòu)→物理結(jié)構(gòu)→基本運(yùn)算→基本算法→算法評價這個脈絡(luò)，研究每特點(diǎn)選擇合適的數(shù)據(jù)結(jié)構(gòu)，進(jìn)一步理解研究數(shù)據(jù)結(jié)構(gòu)的意義。2．教學(xué)方法采用引導(dǎo)、啟發(fā)、研究、討論、問題驅(qū)動等多種形員的想象力和創(chuàng)新能力。3．教學(xué)手段采用多媒體和板書相結(jié)合的形式，全方位、多角度想更為形象、直觀，提高學(xué)生的學(xué)習(xí)興趣和求知欲。4．以知識驗(yàn)證、知識綜合、創(chuàng)新設(shè)計(jì)為原則，設(shè)計(jì)上機(jī)實(shí)驗(yàn)內(nèi)理論授課內(nèi)容，貫徹“學(xué)以致用”的思想。教學(xué)進(jìn)度總體安排課堂教學(xué)實(shí)踐教學(xué)網(wǎng)絡(luò)教序號教學(xué)內(nèi)容學(xué)時學(xué)時學(xué)學(xué)時1概述22表結(jié)構(gòu)1863樹結(jié)構(gòu)1864圖結(jié)構(gòu)104學(xué)員自5排序82主學(xué)習(xí)6集合運(yùn)算227算法設(shè)計(jì)的一般方法2總計(jì)6020教學(xué)進(jìn)度具體安排第一章概述………4學(xué)時第1講《算法和數(shù)據(jù)結(jié)構(gòu)》概述……………2學(xué)時第30講算法設(shè)計(jì)的一般方法………………2學(xué)時第二章表結(jié)構(gòu)……………18學(xué)時第2講表結(jié)構(gòu)的概念…………………2學(xué)時第3講順序表的運(yùn)算…………………2學(xué)時第4講鏈表的基本概念…………………2學(xué)時第5講簡單鏈表的運(yùn)算………………2學(xué)時第6講復(fù)雜鏈表及鏈表的應(yīng)用…………2學(xué)時第7講棧和隊(duì)…………2學(xué)時第8講靜態(tài)鏈表………2學(xué)時第9講矩陣運(yùn)算………2學(xué)時第10講字符串………2學(xué)時第三章樹結(jié)構(gòu)……………18學(xué)時第11講樹結(jié)構(gòu)的概念…………………2學(xué)時第12講二叉樹……………2學(xué)時第13講二叉樹的遍歷……2學(xué)時第14講遍歷算法的應(yīng)用…………………2學(xué)時第15講遍歷序列的性質(zhì)…………………2學(xué)時第16講二叉樹的構(gòu)造……2學(xué)時第17講檢索樹……………2學(xué)時第18講平衡樹……………2學(xué)時第19講哈夫曼樹、判定樹………………2學(xué)時第四章圖結(jié)構(gòu)……………10學(xué)時第20講圖的概念和存儲結(jié)構(gòu)………………2學(xué)時第21講先深搜索和先廣搜索………………2學(xué)時第22講最小生成樹…………2學(xué)時第23講最短路徑……………2學(xué)時第24講有向無回路圖、雙連通分量………2學(xué)時第五章排序……………8學(xué)時第25講基本概念、插入排序…………2學(xué)時第26講交換排序………2學(xué)時第27講選擇排序…………2學(xué)時第28講合并排序、基數(shù)排序……………2學(xué)時第六章集合運(yùn)算……………2學(xué)時第29講散列表……………2學(xué)時說明：為了空出一次復(fù)習(xí)課的時間，在實(shí)施計(jì)劃中將第11講和第12講壓縮為了一次課。內(nèi)容備注第一章概述第1講《算法和數(shù)據(jù)結(jié)構(gòu)》概述講課題目：《算法和數(shù)據(jù)結(jié)構(gòu)》概述（1.1、1.2、1.3）目的要求：1．了解課程基本信息，建立基本要求2．掌握基本數(shù)據(jù)結(jié)的構(gòu)特征及其意義3．掌握算法的定義和三種描述方式4．了解算法的評價方法知識點(diǎn)：1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念2．算法的描述和實(shí)現(xiàn)3．算法的評價方法重點(diǎn)難點(diǎn)：1．表、樹、圖結(jié)構(gòu)的特征及其意義2．算法的定義，算法的描述方式3．算法的時間復(fù)雜性方法步驟：1．介紹與課程有關(guān)的相關(guān)知識2．從求解問題的一般步驟入手，建立抽象的數(shù)據(jù)模型（數(shù)值、非數(shù)值）3征4．用示例介紹算法的描述形式和適用場合，研究算法“好問題的意義和價值，站在使用效果、滿足需要等角度，討論研究評價算法的標(biāo)準(zhǔn)。器材保障：電腦、投影儀、教鞭教學(xué)內(nèi)容與時間安排:一、課程基本信息10分鐘內(nèi)容備注（一）教員信息主講教員：陳衛(wèi)衛(wèi)聯(lián)系方式：824546(O)，828596(H)E_mail：hchcww@263.net辦公室：教學(xué)樓809（二）課程的主要任務(wù)使學(xué)員獲得算法和數(shù)據(jù)結(jié)構(gòu)方面的基本知識，培養(yǎng)學(xué)員的程序設(shè)計(jì)能力和初級算法設(shè)計(jì)能力，掌握運(yùn)用計(jì)算機(jī)解決本專業(yè)實(shí)際問題的基本方法，為今后的工作和學(xué)習(xí)奠定堅(jiān)實(shí)的基礎(chǔ)。（三）教學(xué)重點(diǎn)和基本條件1．教學(xué)重點(diǎn)在于圍繞算法指導(dǎo)學(xué)生編程，使學(xué)生知道什么是“好”的算法，如何才能學(xué)會編寫高質(zhì)量的程序。2．基本條件：熟練使用C語言（C++掌握VC++6.0集成開發(fā)環(huán)境（四）教材及參考書目1．教材(TextBook)《數(shù)據(jù)結(jié)構(gòu)教程》王慶瑞編著北京希望電子出版社2．參考書一般的《DataStructuresandAlgorithmAnalysisinCSecondEditionMarkAllenWeiss著，陳越改編，北京：人民郵電出版社，2005數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏、吳偉民編著清華大學(xué)出版社C算法（第一卷，基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、排序和搜索第三版）AlgorithmsINC(THIRDEDITION)C算法（第二卷圖算法）RobertSedgewick著周良忠譯，人民郵電出版社POSTS&TELECOMPRESS經(jīng)典的計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（第3版）TheArtofComputerProgramming第1卷基本算法內(nèi)容備注第2卷半數(shù)值算法第3卷排序與查找DonaldE.Knuth著蘇運(yùn)霖譯，國防工業(yè)出版社AddisonWesley，2003結(jié)合課程（五）學(xué)習(xí)方法特點(diǎn)，強(qiáng)調(diào)認(rèn)真聽講讀書、思考好的學(xué)習(xí)獨(dú)立完成作業(yè)方法。上機(jī)練習(xí)（六）評價方式平時作業(yè)（含上機(jī)）上課表現(xiàn)筆試試卷二、數(shù)據(jù)結(jié)構(gòu)的概念20分鐘（一）問題的求解過程1．解題的一般過程接受任務(wù)（設(shè)計(jì)程序、軟件）針對問題進(jìn)行分析設(shè)計(jì)出求解策略，即算法（algorithm“問題級的算法（或初級算法）算法的需要，抽象出所要處理的數(shù)據(jù)建立數(shù)據(jù)結(jié)構(gòu)將算法分解成對數(shù)據(jù)結(jié)構(gòu)的運(yùn)算設(shè)計(jì)出對數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法（數(shù)據(jù)結(jié)構(gòu)級算法）對算法的性能（可行性和運(yùn)行效率：時間和空間）進(jìn)行評估著手程序設(shè)計(jì)對程序進(jìn)行調(diào)試交付使用2．程序與算法的關(guān)系程序是按算法思想進(jìn)行設(shè)計(jì)的，程序中含有算法。內(nèi)容備注（二）數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)1．?dāng)?shù)據(jù)從狹義和能處理的一切符號的總稱，是程序加工的對象和產(chǎn)品。廣義兩個2．?dāng)?shù)據(jù)的種類角度闡述數(shù)值型數(shù)據(jù)（整數(shù)、實(shí)數(shù)等）：例，四則運(yùn)算文字型數(shù)據(jù)（字符、字符串）：例，文本文件，程序代碼（編譯軟件）數(shù)據(jù)。聲音、圖像形式的數(shù)據(jù)：例，mp3、avi。數(shù)據(jù)總是以某種編碼形式出現(xiàn)的。3舉例說明數(shù)據(jù)元素的集合，元素之間的關(guān)系，對數(shù)據(jù)和數(shù)據(jù)集合進(jìn)行哪些運(yùn)算，如何提高運(yùn)算效率。4．?dāng)?shù)據(jù)元素（dataelement）node質(zhì)的一組相關(guān)信息組成一個數(shù)據(jù)結(jié)點(diǎn)。通常，一個結(jié)點(diǎn)含有多個數(shù)據(jù)項(xiàng)（記錄型結(jié)點(diǎn)，或結(jié)構(gòu)型結(jié)點(diǎn)）每個數(shù)據(jù)項(xiàng)是結(jié)點(diǎn)的一個域（field（key例如：（1點(diǎn)的關(guān)鍵字域。（2期。5．?dāng)?shù)據(jù)結(jié)構(gòu)（datastructure）《數(shù)據(jù)結(jié)構(gòu)》是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象

以及它們之間的關(guān)系和處理算法的學(xué)科。（1）定義：數(shù)據(jù)結(jié)構(gòu)B=(D，R)——邏輯結(jié)構(gòu)

D：有窮的結(jié)點(diǎn)集合；R：D中結(jié)點(diǎn)間的有窮關(guān)系集合注意內(nèi)容備注（2）研究內(nèi)容數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系、存儲方式、基本運(yùn)算、實(shí)現(xiàn)運(yùn)算的算法、算法評價方法。“好”數(shù)據(jù)結(jié)構(gòu)＋“好”算法＝“好”程序良好、合理的數(shù)據(jù)結(jié)構(gòu)清晰、實(shí)用的算法簡潔、高效的程序（3）數(shù)據(jù)結(jié)構(gòu)的兩個方面1立起來的，呈現(xiàn)在用戶面前的結(jié)構(gòu)形式。2內(nèi)的表示方法，即存儲形式。既要存儲數(shù)據(jù)，又要（存儲）體現(xiàn)出邏輯結(jié)構(gòu)。主要概念有：存儲結(jié)點(diǎn)：用于存儲一個數(shù)據(jù)結(jié)點(diǎn)的存儲單元。一個數(shù)據(jù)結(jié)點(diǎn)對結(jié)點(diǎn)、自由結(jié)點(diǎn)。6．常見的邏輯數(shù)據(jù)結(jié)構(gòu)表、樹、圖、集合（1）表：描述結(jié)點(diǎn)之間簡單的先后次序關(guān)系。一對一關(guān)系（2）樹：描述結(jié)點(diǎn)之間的層次關(guān)系，或嵌套關(guān)系。一對多關(guān)系（3）圖：描述結(jié)點(diǎn)之間的“多對多”關(guān)系。（4）集合：結(jié)點(diǎn)之間的“無關(guān)關(guān)系。結(jié)構(gòu)中的數(shù)據(jù)元素之間除“同屬于一個集合”的關(guān)系，無其他關(guān)系。7．基本存儲結(jié)構(gòu)從存儲角度看，數(shù)據(jù)結(jié)構(gòu)可以歸結(jié)為兩種基本結(jié)構(gòu)：（1）順序存儲結(jié)構(gòu)把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。（2）鏈接存儲結(jié)構(gòu)不要求邏輯上相鄰的結(jié)點(diǎn)其物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針域表示的。內(nèi)容備注8．運(yùn)算（operation）：對數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的處理操作。不同的數(shù)據(jù)結(jié)構(gòu)有不同的運(yùn)算。如表結(jié)構(gòu)的常見運(yùn)算：查找、插入、刪除、排序等。（1）插入(Insert)在數(shù)據(jù)結(jié)構(gòu)的指定位置上增添新的數(shù)據(jù)元素。闡述運(yùn)算（2）刪除(Delete)刪去數(shù)據(jù)結(jié)構(gòu)中某個指定的數(shù)據(jù)元素。（3）更新(Update)及關(guān)聯(lián)關(guān)改變數(shù)據(jù)結(jié)構(gòu)中某個數(shù)據(jù)元素的值，在概念上等價于刪除和插入操作的組合。的運(yùn)算一（4）查找(Search)在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個特定要求的數(shù)據(jù)元素(位置或值)。三、算法的描述和實(shí)現(xiàn)30分鐘（一）算法(Algorithm)的定義1．簡單定義：算法記載了求解問題的方法和步驟。算法(Algorithm)有限時間完成的、毫不含糊的指令的有限序列。其中每一條指令表示一個或多個操作。2．克努特（D.E.Knuth）的定義：算法就是一個有窮規(guī)則的集合。規(guī)則規(guī)定解決某一特定問題的運(yùn)算序列。算法的5個重要特性。有窮性、確定性、輸入、輸出、可行性（算法中所（1）有窮性：執(zhí)行有限步，每步均在有窮時間內(nèi)完成。（2）確定性：對相同的輸入，必產(chǎn)生相同的輸出，即無二義性。（3）可行性：計(jì)算機(jī)可使用已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來完成。（4）輸入：零個或多個輸入。（5）輸出：一個或多個輸出。（二）算法的存在形式1．程序形式程序形式——算法的實(shí)現(xiàn)——算法的最終形式。2．描述形式內(nèi)容備注描述形式：便于理解、記憶和互相交流三種描述形式：形式化、半形式化、非形式化。3．形式化描述——用類語言描述的形式——“半程序形式。偽程序（偽類語言：以某種程序設(shè)計(jì)語言（C略加改造而形成的語言。/輸出等細(xì)節(jié)，保留程序的基本框架。偽程序與“真程序”非常接近，略加改造就是真程序。4．半形式化5．非形式化——文字?jǐn)⑹鲂问?，最原始形式?．示例例1.1自然選擇排序算法。把一組（共n個）雜亂數(shù)據(jù)排列成由小到大的遞增序列。

simpleselectionsort（1）文字?jǐn)⑹鲂问剑合葟膎個數(shù)據(jù)中選出一個最小元素，使它作為序列的第一項(xiàng)；再從剩下的

n-1個數(shù)據(jù)中選出一個最小元素作為第二項(xiàng)……，重復(fù)地作上述選擇工作，

直至選擇最后一項(xiàng)。最終將得到有序序列。算法不依賴數(shù)據(jù)結(jié)構(gòu)，不考慮數(shù)據(jù)是如何存儲的。（2）進(jìn)一步敘述：假定數(shù)據(jù)存儲在數(shù)組a[n]中：先從a的n個元素中選擇一個最小元素（比如某個a[j]a[0]交換位置；再從剩下的n-1個元素中選擇一個最小元素，將它與a[1]交換位置；再從剩下的n-2個元素中選擇一個最小元素，將它與a[2]交換位置；……反復(fù)進(jìn)行上述選擇和交換，直到選擇出最后一個元素，從而完成排序工作。（3）用類C程序（形式化）：for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;內(nèi)容備注w=a[i];a[i]=a[k];a[k]=w;}例1.2二分查找（binarysearch）算法。在元素從小到大排列的有序數(shù)組a[n]xx在數(shù)組a中出現(xiàn)，就用變量i記住它所在的數(shù)組下標(biāo)，若x不出現(xiàn)，則i=-1。二分查找算法：（1）文字?jǐn)⑹霾襟E1置left和right的初值，即left=0，right=n-1；步驟2如果left>righta中沒有x使i=-1法終止；否則：步驟3計(jì)算中值地址，即下標(biāo)mid=(left+right)/2；步驟4比較x與a[mid]的值：（4.1）如果x=a[mid]，則找到x，i=mid，算法終止；否則，（4.2x<a[mid]rightright=mid-12繼續(xù)查找；（4.3）如果x>a[mid]，則調(diào)整左指針left，使left=mid+1，轉(zhuǎn)到步驟2繼續(xù)查找。這樣，反復(fù)執(zhí)行步驟（2）到（4（2）流程圖：P5圖1.3二分查找算法的流程圖

7．三種算法描述形式小結(jié)（1義性。（2）流圖：直觀、結(jié)構(gòu)更清晰，容易理解，接近程序形式；也有二義性，比較麻煩，不容易修改。常用于對大型軟件的結(jié)構(gòu)分析和說明。（3）偽代碼形式：克服二義性，突出算法的主體，保持算法的良好結(jié)構(gòu)，可采用逐步求精的程序設(shè)計(jì)方法。便于對算法時間、空間作定量的分析。8．算法和程序的關(guān)系程序（Program）是用計(jì)算機(jī)程序設(shè)計(jì)語言實(shí)現(xiàn)的完成一定功能的代碼。算法的程序形式稱為算法的實(shí)現(xiàn)（例如，C式。程序中體現(xiàn)了算法的思想。算法不依賴于具體的實(shí)現(xiàn)語言。內(nèi)容備注程序中有算法，算法不一定是程序。四、算法的評價標(biāo)準(zhǔn)5分鐘（一）算法分析對算法的綜合性能進(jìn)行較為客觀的分析評價評估，評測（二）評價角度（標(biāo)準(zhǔn)）1．算法的正確性(Correctness)能滿足具體問題的需求，且所有合法的輸入數(shù)據(jù)都正確才算正確。評價方法：調(diào)試只能證明算法有錯，不能證明算法無錯。人工證明（歸納法）2．算法的有效性（算法的運(yùn)行效率）算法的運(yùn)行效率(Efficiency)——耗用時間，占用空間。（1timecomplexity）：對時間的客觀要求。同一問題，算法執(zhí)行時間越短，效率越高。（2）算法的空間復(fù)雜性（spacecomplexity）：對空間的客觀要求。指算法執(zhí)行過程中所需的最大存儲空間。3．對程序（軟件）評價的附加標(biāo)準(zhǔn)（1）操作界面（2）健壯性(Robustness)對于異常的處理能力。能作出判斷，并給出適當(dāng)?shù)奶崾净蚓嫘畔?，以?/p>

待操作員的干預(yù)或能自動進(jìn)行適當(dāng)處理。（3）可讀性(Readability)希望一個算法易于理解、易于編碼，也易于調(diào)試。（4）可維護(hù)性等等。五、算法的時間復(fù)雜性20分鐘（一）算法的時間復(fù)雜性函數(shù)分析計(jì)算法時間復(fù)雜性的困難之處，剖內(nèi)容備注1．T(n)n描述算法執(zhí)行過程中所需的時間用量與問題規(guī)模n之間的函數(shù)關(guān)系T(n)。T(n)要計(jì)算得“精確（客觀）很因難。2．計(jì)算的困難性執(zhí)行時間取決于下列因素：問題的規(guī)模（輸入的大小/復(fù)雜程度）所選用的語言編譯程序所產(chǎn)生可執(zhí)行代碼的質(zhì)量機(jī)器執(zhí)行指令的速度（二）可能的方法1．事后統(tǒng)計(jì)思考：用具體的時分秒度量可以嗎？2．事前估計(jì)事先估算的主要因素——問題的規(guī)模。例6：兩個n×n矩陣相乘，令數(shù)乘作為基本運(yùn)算for(i=1;i<=n;i++)for(j=1;j<=n;j++){C[i][j]=0;for(k=1;k<=n;k++)C[i][j]+=A[i][k]*B[k][j];};整個算法執(zhí)行時間與數(shù)乘次數(shù)n3成正比，記作T(n)=O(n3)兩個n×n矩陣相乘的時間復(fù)雜度為O(n3)。（三）時間度量單位明確度量單位的意T(n)等于執(zhí)行基本語句的總條（次）數(shù)。大體上能夠說明算法的時間性能。義，學(xué)會把（四）大“O”記號內(nèi)容備注1．T(n)的上界（1）定義對某算法執(zhí)行時間T(n)c和n0n>n0T(n)≤cf(n)都成立。即T(n)≤cf(n)（c是任意正的常數(shù)——常系數(shù)，f(n)那么，就記作T(n)=O(f(n))O(f(n))率的一個上界為f(n)，或說T(n)是f(n)的大O函數(shù)。（2）內(nèi)涵只求出T(n)隨輸入數(shù)據(jù)量n而增長的趨勢（極限情況）——算法的漸近時間復(fù)雜性（asymptotictimecomplexity形式，只求出T(n)的“階。只求出T(n)的最高階，忽略其低階項(xiàng)和常系數(shù)。（3）示例設(shè)T(n)=n2+4n，則有f(n)=n2，即有：n2+4n=O(n2)因?yàn)榇嬖赾=2，n0=4，使對于一切n>n0，恒有n2+4n≤2n22．優(yōu)點(diǎn)（1）簡化T(n)的計(jì)算（2）比較客觀地反映出當(dāng)n很大時，算法的時間性能。3．示例對某問題，設(shè)計(jì)了兩個算法，經(jīng)過計(jì)算得出：算法A的時間耗費(fèi)函數(shù)為T1(n)=20n2+100n算法B的時間耗費(fèi)函數(shù)為T2(n)=0.5n2－3n+18這兩個算法的時間耗費(fèi)函數(shù)的階是一樣的，都是n的平方階的，于是可以寫成T1(n)=O(n2)T2(n)=O(n2)當(dāng)n很大時，低階算法比高階算法好。內(nèi)容備注4．常用階O(1)常數(shù)時間，即算法時間用量與輸入數(shù)據(jù)量n的大小無關(guān)O(logn)對數(shù)時間，對數(shù)階通常不寫底數(shù)（底數(shù)無關(guān)）因?yàn)槿魏纬?shù)C1，C2>0，有O(logc2n)=O(logc1c2logc1n)=O(logc1n)因?yàn)閘ogc1c2是常數(shù)O(n)線性時間，即算法時間用量與n成正比O(nlogn)非常理想的階O(n2)平方階O(n3)立方階……T(n)=O(nd)d“有效算法。O(2n)指數(shù)階O(n!)階乘階則是無效算法，當(dāng)n稍大一點(diǎn)，就不能在“有限的”時間內(nèi)完成。示例：某算法的時間復(fù)雜性T(n)=2n，當(dāng)n=1000時，其工作量（執(zhí)行基本21000110-9秒）時間，那么解此問題共需要：（五）最壞情況和平均情況1．為什么要區(qū)分兩種情況若某算法，對不同的輸入數(shù)據(jù)（輸入數(shù)據(jù)量都是n）耗用時間的差別很大，為使評價更客觀，更有說服力，所以需要分幾種情況討論算法的時間性能。最壞情況（worst-case）和平均情況（expected-case態(tài)和平均性態(tài)。從這兩個角度分析算法的時間性能，可以給算法作出更為客觀的評價。舉例說明2．最壞情況區(qū)分最壞對于具有相同輸入數(shù)據(jù)量的不同輸入數(shù)據(jù)，算法時間用量的最大值。用TW(n)表示最壞情況。3．平均情況情況和平均情況的對于所有相同輸入數(shù)據(jù)量的各種不同數(shù)據(jù)，算法耗用時間的平均值。重要意義。內(nèi)容備注用TE(n)表示平均情況下算法時間復(fù)雜性。4．注意（1）一般不討論“最好”情況下算法的時間復(fù)雜性。（2兩種不同情況了?；\統(tǒng)地用T(n)表示算法時間。三、算法的空間復(fù)雜性5分鐘1．算法空間用量函數(shù)S(n)通常只計(jì)算輔助空間用量，而不計(jì)原始數(shù)據(jù)所占的空間。2．示例自然選擇排序算法。for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;w=a[i];a[i]=a[k];a[k]=w;}原始數(shù)據(jù)占用空間：n輔助空間（“純”空間）：4（i，j，w，k）S(n)=O(1)3．時空轉(zhuǎn)換四、計(jì)算時間復(fù)雜性的一般方法10分鐘（一）典型語句度量法1“最多”是指：其他語句花費(fèi)時間的總和將不超過這個語句花費(fèi)時間的常數(shù)倍。用典型語句的執(zhí)行次數(shù)度量這段程序花費(fèi)時間的階。若這段程序形如，語句1；語句2；……內(nèi)容備注語句s；……語句m;假定語句s共執(zhí)行f(n)次，除語句s外，其他語句執(zhí)行次數(shù)總和不超過cf(n)次（c是常數(shù)，即與nf(n)+cf(n)=(c+1)f(n)根據(jù)漸近復(fù)雜性的定義，這段程序的時間耗費(fèi)是O(f(n))。注意：這樣的語句可能不止一條。2．示例注意：示意性程序：for(i=1,c=0,s=a[0];i<n;i++)語句序號{（123）1.if(a[i]<a[0])//統(tǒng)計(jì)小于a[0]的元素個數(shù)2.c+=1;不是程序3.s+=a[i];//計(jì)算數(shù)組元素的總和的一部分，}可選句1n-1O(n)

O(n)。3．典型語句的選擇方法（1）一般情況，可以任選。但是要符合“最多”要求。

（2（與多少個元素比

較過）度量時間用量。（3量算法的時間用量。在算法理論上，分為“算法類。（二）分段計(jì)算法若一段耗時為O(f(n))，另一段耗時為O(g(m))，那么兩段共耗費(fèi)O(f(n))+O(g(m))=O(f(n)+g(m))例如，O(n2)+O(n)=O(n2)內(nèi)容備注O(n)+O(n)=O(n)（三）分層計(jì)算法分層相乘，再化簡1．簡單相乘若外層循環(huán)共執(zhí)行O(f(n))O(g(m))次，那么兩層共執(zhí)行O(f(n))O(g(m))=O(f(n)g(m))次。示例：示意性程序：for(i=0;i<n;i++)1.{x=y=0;for(j=0;j<n/2;j++)2.{if(a[j]>a[i])x+=1;3.if(a[j]<a[i])y+=1;priintf("%d,%d\n",x,y);}}外循環(huán)共執(zhí)行n次，外循環(huán)每執(zhí)行一次，內(nèi)循環(huán)都執(zhí)行n/2次，注意到O(n/2)=O(n)，所以本段程序時間復(fù)雜性為O(n)*O(n)=O(n2)注意：分層相乘有時不夠精確，過于“粗糙。可能會算多了。2．直接計(jì)算內(nèi)循環(huán)總的執(zhí)行次數(shù)例如，for(i=1;i<=n;i++)for(j=1;j<=i;j++)printf("%d",i*j);顯然，外循環(huán)第i次執(zhí)行時，內(nèi)循環(huán)執(zhí)行i次，所以內(nèi)循環(huán)總的執(zhí)行次數(shù)等于（四）遞推式方法過求解遞歸方程，計(jì)算出時間復(fù)雜性。示例：焚塔問題的時間耗費(fèi)。用T(n)表示搬動高度為n的塔所需的移動總次數(shù)，那么可得出下列遞歸方程：內(nèi)容備注（五）其他方法利用“便于”計(jì)算的數(shù)學(xué)模型，和復(fù)雜的數(shù)學(xué)演算（包括微分和積分運(yùn)T(n)。（六）算法的選用原則需要考慮如下因素。算法實(shí)現(xiàn)的難易程度。算法運(yùn)行環(huán)境（輸入數(shù)據(jù)量的大小范圍）當(dāng)數(shù)據(jù)量不大時，低階算法未必就快。例如，算法A1和A2的時間復(fù)雜性分別為T1(n)=1000n和T2(n)=n2雖然O(T1(n))<O(T2(n))，但是只有當(dāng)n>1000時，A1才好于A2；而當(dāng)n≤1000時，A2卻好于A1，因?yàn)門2(n)≤T1(n)。小結(jié)：1．?dāng)?shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、研究對象、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)2．常見的4種基本數(shù)據(jù)結(jié)構(gòu)及特點(diǎn)3．基本運(yùn)算4．算法的描述方式5．算法的評價標(biāo)準(zhǔn)（正確性、有效性）6．時間復(fù)雜性（大O作業(yè)：P251.1、1.2（選）思考題：1．列舉一些你知道的數(shù)值類問題的數(shù)學(xué)模型。參考資料：[1]MarkAllenWeiss著，陳越改編，《DataStructuresandAlgorithmAnalysisinCSecondEdition人民郵電出版社，2005內(nèi)容備注[2]2003[3]王曉東編著，算法設(shè)計(jì)與分析，北京：清華大學(xué)出版社，2003本次課教學(xué)體會：第30講算法設(shè)計(jì)的一般方法（簡介）講課題目：算法設(shè)計(jì)的一般方法目的要求：1．了解有效算法設(shè)計(jì)方法2．了解遞歸方法、分治方法、動態(tài)規(guī)劃法、貪心法、搜索-回溯法、平衡原則。知識點(diǎn)：遞歸、分治法、貪心法、動態(tài)規(guī)劃、平衡原則、回溯重點(diǎn)難點(diǎn)：各種算法設(shè)計(jì)方法的特點(diǎn)、可以解決的問題方法步驟：1．舉例介紹問題，總結(jié)歸納方法器材保障：電腦、投影儀、教鞭教學(xué)內(nèi)容與時間安排:一、算法設(shè)計(jì)的一般方法5分鐘算法——“無法”靠人們的智慧和靈感，針對不同問題設(shè)計(jì)不同算法。-回溯法、平衡原則。二、遞歸（recursion）30分鐘（一）好處結(jié)構(gòu)簡單清晰，易于閱讀和理解。另外，便于寫T(n)的遞歸推式，求出T(n)（使用組合論方法）（二）要求將問題寫成遞歸定義形式內(nèi)容備注（三）描述工具——（充分必要）遞歸函數(shù)。（四）種類有直接遞歸和間接遞歸兩種遞歸方式1．直接遞歸函數(shù)p中含有調(diào)用自身的語句2．間接遞歸函數(shù)（聯(lián)立遞歸）函數(shù)p調(diào)用函數(shù)q，而q又直接或間接地調(diào)用p。（五）終止條件（初始條件）（六）示例例1.3二分查找的遞歸算法。例1.4焚塔（Hanoitower）游戲。（七）單調(diào)遞歸和非單調(diào)遞歸1．每執(zhí)行一次，至多產(chǎn)生一次遞歸。很容易改成非遞歸形式。2（八）遞歸與其他技術(shù)相結(jié)合，可以導(dǎo)出更有效的算法。三、分治和平衡20分鐘（一）分治法（divide-and-conquertechnique）的基本原理在求解一個規(guī)模較大的問題時，可以把它分解成若干個規(guī)模較小的問題，并遞歸地把各子問題再次細(xì)分，直到問題“小到”容易求解為止，求出各子問題的解之后，再把這些解合成原問題的解。（二）示例例1.5求n個（n≥2）元素集合S的最大元素和最小元素問題。1．直觀方法用2n-3次比較。2．分治法把SS1和S2S1和S2內(nèi)容備注個最小元素選出一個較小的，它們分別是S的最大元素和最小元素。算法1.5（假設(shè)n=2kP16，半程序形式3．實(shí)現(xiàn)方法用數(shù)組a[n]存儲集合。一對下標(biāo)“限制”集合范圍。4．時間復(fù)雜性列出比較次數(shù)的遞推方程。很容易用迭代法求出式(1.2)的解是（三）采用分治法的條件和原則1．所求解的問題容易分解成子問題。2．容易把子問題的解合成原問題的解。3．劃分工作量要少。4．要遵循平衡（balance）原則，也就是要盡量使分解出的子問題大小相等，并且子問題的個數(shù)和子