數(shù)據(jù)結(jié)構(gòu)與算法：第1章 緒論

數(shù)據(jù)結(jié)構(gòu)與算法DataStructures

andAlgorithm講課學(xué)時(shí)：42，實(shí)驗(yàn)學(xué)時(shí)：12，課程設(shè)計(jì)：18+1周教學(xué)安排：期末考試占60%，實(shí)驗(yàn)成績(jī)占30%，平時(shí)作業(yè)占10%考核要求：本學(xué)期上課時(shí)間：3-14周,周二5-6節(jié)，周四5-6節(jié).致知23考試時(shí)間：18周課程設(shè)計(jì)：12-16周計(jì)算機(jī)導(dǎo)論數(shù)字邏輯計(jì)算機(jī)組成技術(shù)操作系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)課程設(shè)計(jì)計(jì)算機(jī)網(wǎng)絡(luò)編譯原理數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)多核程序設(shè)計(jì)數(shù)據(jù)庫(kù)系統(tǒng)Linux操作系統(tǒng)*程序設(shè)計(jì)語(yǔ)言用戶界面設(shè)計(jì)面向?qū)ο蠹夹g(shù)與UMLJava語(yǔ)言程序設(shè)計(jì)實(shí)踐面向服務(wù)的計(jì)算技術(shù).NetC++語(yǔ)言J2EE軟件開發(fā)實(shí)踐軟件外包開發(fā)技術(shù)*英語(yǔ)限選軍訓(xùn)大學(xué)外語(yǔ)體育政治大學(xué)外語(yǔ)體育馬哲英語(yǔ)限選體育英語(yǔ)限選體育英語(yǔ)口語(yǔ)英語(yǔ)限選英語(yǔ)口語(yǔ)工科數(shù)析Ⅰ代數(shù)與幾何概率論與數(shù)理統(tǒng)計(jì)離散數(shù)學(xué)運(yùn)籌學(xué)算法設(shè)計(jì)與分析工科數(shù)析Ⅱ理論系列系統(tǒng)系列工具系列工程系列管理系列其他課程第一學(xué)期第二學(xué)期第三學(xué)期第四學(xué)期第五學(xué)期第六學(xué)期第七學(xué)期第八學(xué)期系統(tǒng)分析與設(shè)計(jì)軟件工程概論軟件項(xiàng)目管理軟件開發(fā)過(guò)程管理軟件質(zhì)量保證與測(cè)試軟件工程綜合課程設(shè)計(jì)計(jì)算機(jī)職業(yè)道德市場(chǎng)營(yíng)銷知識(shí)產(chǎn)權(quán)法交流技巧財(cái)務(wù)管理商務(wù)談判IT企業(yè)管理合同法IT企業(yè)創(chuàng)業(yè)管理方向課計(jì)算機(jī)安全概論服務(wù)學(xué)概論中文信息處理嵌入式操作系統(tǒng)方向1)網(wǎng)絡(luò)通信與信息安全2)服務(wù)學(xué)與企業(yè)信息化3)多媒體與信息處理4)嵌入式系統(tǒng)與軟件畢業(yè)設(shè)計(jì)物聯(lián)網(wǎng)專業(yè)教材數(shù)據(jù)結(jié)構(gòu)與算法（第4版）編著廖明宏郭福順張巖李秀坤高等教育出版社參考資料數(shù)據(jù)結(jié)構(gòu)嚴(yán)尉敏吳偉民編著清華大學(xué)出版社引進(jìn)教材DataStructuresandProgramDesigninC++數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)——C++語(yǔ)言描述（影印版）RobertL.Kurse,AlexandeerJ.RybaISBN7-04-010039-8/TP.691P736教材比較1.1數(shù)據(jù)結(jié)構(gòu)研究對(duì)象1.2數(shù)據(jù)結(jié)構(gòu)發(fā)展概況1.3抽象數(shù)據(jù)型(ADT)1.4數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)1.5算法描述與算法分析主要內(nèi)容1.1數(shù)據(jù)結(jié)構(gòu)研究對(duì)象◆計(jì)算機(jī)科學(xué)：信息在計(jì)算機(jī)內(nèi)使用數(shù)據(jù)來(lái)表示,

研究信息表示和信息處理。◆數(shù)據(jù)：是用以描述客觀事物的數(shù)值、字符，以及一切可以輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序加以處理的符號(hào)的集合。數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素?cái)?shù)據(jù)的最小單位稱為數(shù)據(jù)項(xiàng)◆數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合◆數(shù)據(jù)特征：數(shù)值、文本、多媒體、超媒體、實(shí)時(shí)、海量◆數(shù)據(jù)類型?高級(jí)語(yǔ)言中變量的取值范圍和允許的操作

什么是數(shù)據(jù)？大數(shù)據(jù)(bigdata)大數(shù)據(jù)可分成：大數(shù)據(jù)技術(shù)大數(shù)據(jù)工程：大數(shù)據(jù)工程指大數(shù)據(jù)的規(guī)劃建設(shè)運(yùn)營(yíng)管理的系統(tǒng)工程；大數(shù)據(jù)科學(xué)：大數(shù)據(jù)科學(xué)關(guān)注大數(shù)據(jù)網(wǎng)絡(luò)發(fā)展和運(yùn)營(yíng)過(guò)程中發(fā)現(xiàn)和驗(yàn)證大數(shù)據(jù)

的規(guī)律及其與自然和社會(huì)活動(dòng)之間的關(guān)系大數(shù)據(jù)應(yīng)用大數(shù)據(jù)的4個(gè)“V”：—Volume：數(shù)據(jù)體量巨大。從TB級(jí)別，躍升到PB級(jí)別；—Variety：數(shù)據(jù)類型繁多。網(wǎng)絡(luò)日志、視頻、圖片、地理位置信息等—Value：價(jià)值密度低。以視頻為例，連續(xù)不間斷監(jiān)控過(guò)程中，可能有用的數(shù)據(jù)

僅僅有一兩秒?！猇elocity：處理速度快，1秒定律。第一，大數(shù)據(jù)的基本概念第二，大數(shù)據(jù)計(jì)算機(jī)其挑戰(zhàn)第三，研究問(wèn)題與部分解大數(shù)據(jù)無(wú)處不在：因特網(wǎng)有很多的大數(shù)據(jù)，在科學(xué)研究領(lǐng)域、醫(yī)療領(lǐng)域、商業(yè)領(lǐng)域、制造業(yè)、智慧城市都有大量的數(shù)據(jù)。全世界的感知數(shù)據(jù)增長(zhǎng)率是每年58%全世界擁有的存儲(chǔ)能力或者是存儲(chǔ)總量的增長(zhǎng)率是每年只有40%2007年，全世界的感知數(shù)據(jù)已經(jīng)超過(guò)了全世界所擁有的存儲(chǔ)器的容量2010年，全世界的感知數(shù)據(jù)是1.25千萬(wàn)PB2011年產(chǎn)生的感知數(shù)據(jù)已經(jīng)二倍于我們?nèi)祟愃鶕碛械拇鎯?chǔ)器的容量結(jié)論：大數(shù)據(jù)無(wú)處不在，數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超出了現(xiàn)有的存儲(chǔ)能力大數(shù)據(jù)的輸入是大數(shù)據(jù)D，問(wèn)題的解是f（D）。李建中教授談大數(shù)據(jù)◆數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素彼此之間抽象的相互關(guān)系，并不涉及數(shù)據(jù)元素的具體內(nèi)容◆數(shù)據(jù)結(jié)構(gòu)分類：線性表：(a1,a2,a3,……ai-1,ai,ai+1……an-1,an)→線性結(jié)構(gòu)線性表的一般概念、字符串、數(shù)組，廣義表等樹：

→層次結(jié)構(gòu)二叉樹，樹等圖：

→網(wǎng)狀結(jié)構(gòu)有向圖、無(wú)向圖等①②③⑤

二叉樹①②③④有向圖◆結(jié)構(gòu)：關(guān)系

國(guó)際象棋：每次需要考慮的合乎規(guī)則的著法平均只有35

步“回合”，計(jì)算機(jī)預(yù)先分析7至8個(gè)回合的著

法。若設(shè)為7個(gè)回合，則有超過(guò)1億億億個(gè)不

同的變化，經(jīng)簡(jiǎn)化后，仍有500億至600億個(gè)

變化。多分析一步，增加18億個(gè)變化資料：下棋程序圍棋：分析7個(gè)回合的著法，則需要考慮超過(guò)200的

14次方個(gè)變化，經(jīng)簡(jiǎn)化后，仍有1000億億個(gè)

變化。多分析一步，增加64萬(wàn)億個(gè)變化根據(jù)計(jì)算機(jī)“深藍(lán)”的速度，平均5分鐘走一步根據(jù)計(jì)算機(jī)“深藍(lán)”的速度，平均1.5年走一步BlueGene,共裝有32個(gè)并行處理器，速度：2億步棋/秒深藍(lán)vs

卡斯帕羅夫:第一次1996年：2月10日—17日，比分2:4第二次1997年：5月3日—11日，比分3.5:2.5雙方先后共進(jìn)行6局對(duì)弈第一局，卡斯帕羅夫執(zhí)白先行，經(jīng)過(guò)3個(gè)多小時(shí)的苦戰(zhàn)擊敗“深藍(lán)”，力拔頭籌；第二局，“深藍(lán)”卻以凌厲的攻勢(shì)和明顯的優(yōu)勢(shì)戰(zhàn)勝卡氏，扳回一局；第三、第四和第五局，雙方下得異常激烈，鏖戰(zhàn)數(shù)小時(shí)，平局；第六局，“深藍(lán)”執(zhí)白先行，一路強(qiáng)攻，僅用一個(gè)多小時(shí)，雙方僅走19步，就讓卡氏俯首稱臣，取得了決定性的勝利。IBM：“深藍(lán)”與棋王卡斯帕羅夫的對(duì)比:身高：卡斯帕羅夫5英尺10英寸，“深藍(lán)”6英尺5英寸；體重：卡斯帕羅夫176磅，“深藍(lán)”1.4噸；年齡：卡斯帕羅夫34歲，“深藍(lán)”4歲；每秒行棋速度：卡斯帕羅夫2步，“深藍(lán)”2億步?！吧駚?lái)之手”1.1數(shù)據(jù)結(jié)構(gòu)研究對(duì)象◆數(shù)據(jù)結(jié)構(gòu)研究方法：邏輯結(jié)構(gòu)：對(duì)操作對(duì)象的一種數(shù)學(xué)描述，或從操作對(duì)象中抽象出的數(shù)學(xué)模型，用以描述數(shù)據(jù)元素之間的邏輯關(guān)系物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示或映象，

物理結(jié)構(gòu)又稱存儲(chǔ)結(jié)構(gòu)，分為順序映象和

非順序映象，或稱順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)計(jì)算機(jī)解題過(guò)程：?jiǎn)栴}→數(shù)學(xué)模型→算法→程序→測(cè)試→計(jì)算分析數(shù)據(jù)并確定存儲(chǔ)結(jié)構(gòu)輸入到計(jì)算機(jī)中1.2數(shù)據(jù)結(jié)構(gòu)發(fā)展概況●數(shù)據(jù)結(jié)構(gòu)側(cè)重解決非數(shù)值問(wèn)題■FORTRAN,ALGOL等高級(jí)語(yǔ)言是以程序?yàn)橹行膫?cè)重于解決數(shù)值問(wèn)題■LISP,SONBOL表或串處理語(yǔ)言是以數(shù)據(jù)為中心側(cè)重于解決非數(shù)值問(wèn)題●1968年以前，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容大多包含在形如表、樹、圖論、集合代數(shù)論、格、關(guān)系等方面。1968年開始，“數(shù)據(jù)結(jié)構(gòu)”逐漸開始成為獨(dú)立的一門課程?！褡鳛橐婚T專業(yè)基礎(chǔ)課，“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)的核心課程之一，是其他專業(yè)課的基礎(chǔ)。是數(shù)學(xué)、硬件和軟件三者的交叉，很受重視?！鰪腜ASCAL語(yǔ)言開始逐漸形成二者結(jié)合知識(shí)結(jié)構(gòu)1.3抽象數(shù)據(jù)型AbstractDataTypes（ADT）

●軟件系統(tǒng)由數(shù)據(jù)結(jié)構(gòu)、操作過(guò)程和控制機(jī)能三者組成，軟件設(shè)計(jì)是對(duì)三者的抽象過(guò)程，即數(shù)據(jù)抽象、過(guò)程抽象和控制抽象。[定義]：抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型和在該模型上定義

的操作的集合ADT特點(diǎn)：①降低了軟件設(shè)計(jì)的復(fù)雜性②提高了程序的可讀性和可維護(hù)性③程序的正確性容易保證抽象：從眾多事物中舍棄個(gè)別的、非本質(zhì)的屬性，抽出共同的、本質(zhì)性的特征。是形成概念的重要手段，其目的是使復(fù)雜度降低。線性表LIST=(D,R)D={ai|ai

∈Elementset,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：設(shè)L的型為L(zhǎng)IST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變量。所有操作描述為：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)數(shù)學(xué)模型1.3抽象數(shù)據(jù)型（ADT）舉例㈠定義任意線性表類型為L(zhǎng)IST，其中元素類型為Elementtype，設(shè)有線性表L，函數(shù)PURGE用以刪除線性表L中所有重復(fù)出現(xiàn)的元素。VoidPURGE(LISTL){Positionp,q;p=FIRST(L);while(p!=END(L)){q=NEXT(p,L);while(q!=END(L))if(same(RETRIEVE(p,L),RETRIEVE(q,L)))

DELETE(q,L);elseq=NEXT(q,L);p=NEXT(p,L);}}1.3抽象數(shù)據(jù)型（ADT）舉例㈡假設(shè)利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合，設(shè)計(jì)算法求一個(gè)新的集合A=A∪B。VoidUNION(LIST&A；LISTB){positionp;

elementtypee;p=FIRST(B);while(p!=END(B);{e=RETRIEVE(p,B);if(same(LOCATE(e,A),END(A)))

INSERT(e,END(A),A);p=NEXT(p,B);}}1.3抽象數(shù)據(jù)型（ADT）抽象數(shù)據(jù)型的規(guī)格描述△完整性：反映所定義的抽象數(shù)據(jù)型的全部特征△統(tǒng)一性：前后協(xié)調(diào)，不自相矛盾△通用性：適用于盡量廣泛的對(duì)象△不依賴性：不依賴于程序設(shè)計(jì)語(yǔ)言，可以用任意的語(yǔ)言來(lái)描述規(guī)格描述的兩個(gè)方面:語(yǔ)法和語(yǔ)義△語(yǔ)法：給出操作的名稱、I/O參數(shù)的數(shù)目和類型△語(yǔ)義：由一組等式組成，定義各種操作的功能及相互間的關(guān)系例如：抽象數(shù)據(jù)型——棧(Stack)定義：棧是一個(gè)后進(jìn)先出（LIFO）的線性表，所有插入、刪除操作是在表的一端（棧頂）進(jìn)行聚集數(shù)組，鏈表(結(jié)構(gòu)體、記錄)，文件1.3抽象數(shù)據(jù)型（ADT）a1a2······an-1anInsertDeletetopbottom棧底棧頂棧示意圖棧(Stack)示意圖1.3抽象數(shù)據(jù)型（ADT）1.3抽象數(shù)據(jù)型（ADT）typeStack[Elementtype];NEWSTACK()→Stack,PUSH(Elementtype,Stack)→Stack,POP(Stack)→Stack∪{UNDEFINED},TOP(Stack)→Elementtype∪{UNDEFINED},EMPTY(Stack)→Boolean;抽象數(shù)據(jù)型——棧語(yǔ)法：declarestk:Stack,elm:Elementtype;POP(NEWSTACK)=NEWSTACK,POP(PUSH(elm,stk))=stk,TOP(NEWSTACK)=UNDEFINED,TOP(PUSH(elm,stk))=elm,EMPTY(NEWSTACK)=TRUE,EMPTY(PUSH(elm,stk))=FALSE;抽象數(shù)據(jù)型——棧語(yǔ)義：

規(guī)格描述給出操作的名稱,I/O參數(shù)的數(shù)目和類型定義各種操作的功能及相互間的關(guān)系抽象數(shù)據(jù)型的實(shí)現(xiàn)抽象描述→（高級(jí)語(yǔ)言）編寫的程序三條原則：①符合規(guī)格描述的定義

②有盡可能好的通用性

③盡可能獨(dú)立于程序的其他部分多層次抽象技術(shù)自底向上與自頂向下相結(jié)合、由簡(jiǎn)單到復(fù)雜1.3抽象數(shù)據(jù)型（ADT）1.4數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)問(wèn)題解決問(wèn)題的算法實(shí)現(xiàn)算法的程序問(wèn)題總是先于算法程序設(shè)計(jì)的四個(gè)里程碑

①子程序、②高級(jí)語(yǔ)言、③結(jié)構(gòu)程序設(shè)計(jì)、④面向?qū)ο?OOP)結(jié)構(gòu)程序設(shè)計(jì)

①限制使用GOTO語(yǔ)句（基于三種基本結(jié)構(gòu)）

②逐步求精的設(shè)計(jì)方法

③自頂向下的設(shè)計(jì)、編碼與調(diào)試

④主程序員組的組織形式N.Wirth：Programming=Algorithm+DataStructure

程序設(shè)計(jì)=算法+數(shù)據(jù)結(jié)構(gòu)1.4數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)問(wèn)題環(huán)境數(shù)據(jù)結(jié)構(gòu)程序結(jié)構(gòu)讀和寫

程序要完成的任務(wù)可執(zhí)行的操作程序結(jié)構(gòu)基于數(shù)據(jù)結(jié)構(gòu)的根源1.4數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)

“我們對(duì)復(fù)雜性問(wèn)題的最重要的辦法是抽象，對(duì)一個(gè)復(fù)雜問(wèn)題，不應(yīng)馬上用計(jì)算機(jī)指令、數(shù)字與邏輯字來(lái)表示，而應(yīng)該用較為自然的抽象語(yǔ)句來(lái)表示，從而得出抽象程序。抽象程序?qū)Τ橄蟮臄?shù)據(jù)進(jìn)行某些特定的運(yùn)算并用某些合適的記號(hào)（可能是自然語(yǔ)言）來(lái)表示。對(duì)抽象程序作進(jìn)一步的分解，并進(jìn)入下一層的抽象，這樣的精細(xì)化過(guò)程一直進(jìn)行下去，直到程序能被計(jì)算機(jī)接受為止。此時(shí)的程序可能是某種高級(jí)語(yǔ)言或機(jī)器指令書寫的。”——N.wirth基于數(shù)據(jù)結(jié)構(gòu)的jackson設(shè)計(jì)方法：①研究問(wèn)題環(huán)境，確定要處理的數(shù)據(jù)結(jié)構(gòu)②基于數(shù)據(jù)結(jié)構(gòu)，形成程序結(jié)構(gòu)（骨架）③用初等操作來(lái)定義要完成的任務(wù)，并分配初等操作“從上到下，逐步求精”算法（Algorithm）：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令（規(guī)則）的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō),就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中，無(wú)論是形成解題思路還是編寫程序,都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。PersianTextbook(《波斯教科書》)的作者的名字AbuJa'farMohammedibn

M?saal-Khowarizm

（約公元前825年）——從字面上看，這個(gè)名字的意思是“Ja'far

的父親，Mohammed和M?sa

的兒子，Khowarizm

的本地人”。Khowarizm

是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm

寫了著名的書Kitabaljabr

w'al-muqabala(《復(fù)原和化簡(jiǎn)的規(guī)則》)；1.5算法描述與算法分析資料：Algorithm與Logarithm這個(gè)詞一直到1957年之前在Webster'sNewWorldDictionary(《韋氏新世界詞典》)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術(shù))，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程。在中世紀(jì)時(shí)，珠算家用算盤進(jìn)行計(jì)算，而算術(shù)家用算術(shù)進(jìn)行計(jì)算。中世紀(jì)之后，對(duì)這個(gè)詞的起源已經(jīng)拿不準(zhǔn)了，早期的語(yǔ)言學(xué)家試圖推斷它的來(lái)歷，認(rèn)為它是從把a(bǔ)lgiros(費(fèi)力的)+arithmos(數(shù)字)組合起來(lái)派生而成的，但另一些人則不同意這種說(shuō)法，認(rèn)為這個(gè)詞是從“喀斯迪爾國(guó)王Algor”派生而來(lái)的。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實(shí)起源：它來(lái)源于著名的PersianTextbook(《波斯教科書》)的作者的名字AbuJa'farMohammedibn

M?saal-Khowarizm

（約公元前825年）——從字面上看，這個(gè)名字的意思是“Ja'far

的父親，Mohammed和M?sa

的兒子，Khowarizm

的本地人”。Khowarizm

是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm

寫了著名的書Kitabaljabr

w'al-muqabala(《復(fù)原和化簡(jiǎn)的規(guī)則》)；另一個(gè)詞，“algebra”(代數(shù))，是從他的書的標(biāo)題引出來(lái)的，盡管這本書實(shí)際上根本不是講代數(shù)的。逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語(yǔ)字典所說(shuō)明的，這個(gè)詞是由于同arithmetic(算術(shù))相混淆而形成的錯(cuò)拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學(xué)詞典Vollstandiges

MathematischesLexicon(《數(shù)學(xué)大全辭典》)，給出了Algorithmus(算法)一詞的如下定義：“在這個(gè)名稱之下，組合了四種類型的算術(shù)計(jì)算的概念，即加法、乘法、減法、除法”。拉頂短語(yǔ)algorithmus

infinitesimalis(無(wú)限小方法)，在當(dāng)時(shí)就用來(lái)表示Leibnitz(萊布尼茲)所發(fā)明的以無(wú)限小量進(jìn)行計(jì)算的微積分方法。1950年左右，algorithm一詞經(jīng)常地同歐幾里德算法(Euclid'salgorithm)聯(lián)系在一起。這個(gè)算法就是在歐幾里德的《幾何原本》(Euclid'sElements,第VII卷，命題i和ii)中所闡述的求兩個(gè)數(shù)的最大公約數(shù)的過(guò)程(即輾轉(zhuǎn)相除法)。遞歸技術(shù)

——最常用的算法設(shè)計(jì)思想，體現(xiàn)于許多優(yōu)秀算法之中分治法

——分而制之的算法思想，體現(xiàn)了一分為二的哲學(xué)思想模擬法

——用計(jì)算機(jī)模擬實(shí)際場(chǎng)景，經(jīng)常用于與概率有關(guān)的問(wèn)題貪心算法

——采用貪心策略的算法設(shè)計(jì)狀態(tài)空間搜索法

——被稱為“萬(wàn)能算法”的算法設(shè)計(jì)策略隨機(jī)算法

——利用隨機(jī)選擇自適應(yīng)地決定優(yōu)先搜索的方向動(dòng)態(tài)規(guī)劃——常用的最優(yōu)化問(wèn)題解決方法“好”的算法的標(biāo)準(zhǔn)：

①正確性，算法能滿足具體問(wèn)題的需求

②可讀性，首先方便閱讀與交流，其次才是機(jī)器執(zhí)行

③健壯性，輸入錯(cuò)誤時(shí)，能作出反應(yīng)，避免異常出錯(cuò)

④效率與低存儲(chǔ)量要求算法的特征：

①有窮性、②確定性、③輸入、④輸出、⑤能行性對(duì)算法“正確性”的要求：

①不含語(yǔ)法錯(cuò)誤；

②對(duì)于幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果；

③對(duì)精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果；

④對(duì)于一切合法的輸入均得到滿足要求的結(jié)果；算法描述：

①自然語(yǔ)言；②程序設(shè)計(jì)語(yǔ)言；③類語(yǔ)言*；關(guān)于本書采用的類語(yǔ)言描述：

①結(jié)構(gòu)類型說(shuō)明

②輸入輸出約定(cin>>v,cout<<v)

③new和delete

④引入引用類型

⑤其他影響算法執(zhí)行的因素：

①算法實(shí)現(xiàn)后所消耗的時(shí)間**②算法實(shí)現(xiàn)后所占存儲(chǔ)空間的大小*③算法是否易讀、易移植等等其它問(wèn)題影響時(shí)間特性的四個(gè)因素：

①程序運(yùn)行時(shí)輸入數(shù)據(jù)的總量②對(duì)源程序編譯所需的時(shí)間③計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間④程序中指令重復(fù)執(zhí)行的次數(shù)*[定義]語(yǔ)句頻度：語(yǔ)句重復(fù)執(zhí)行的次數(shù)程序運(yùn)行時(shí)間漸近時(shí)間復(fù)雜度（時(shí)間復(fù)雜度）T（n）

算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間度量記作：

T（n）=O（f（n））它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)率相同。漸近空間復(fù)雜度（空間復(fù)雜度）S（n）S（n）=O（g（n））運(yùn)算法則：設(shè)：T1(n)=O(f(n))，T2(n)=O(g(n))

加法規(guī)則：T1(n)+T2(n)=O(max{f(n),g(n)})

乘法規(guī)則：T1(n)·T2(n)=O(f(n)·g(n))程序運(yùn)行時(shí)間比較T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△

T(n)設(shè)：T(x)：取變量或常量x之值所消耗時(shí)間T(.V)：取變量V之地址所消耗的時(shí)間T(=)：賦值所消耗時(shí)間T(θ)：執(zhí)行基本運(yùn)算θ所耗時(shí)間T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時(shí)間T(par)：將參數(shù)par傳給函數(shù)所消耗時(shí)間～(1)表達(dá)式和賦值語(yǔ)句

exp::=常數(shù)|變量|F-name(e1,e2,…,em)|(expθexp)

T(v=exp)=T(.v)+T(=)+T(exp)

T(exp

θ

exp)=T(exp)+T(θ)+T(exp)

T(F-name(e1,e2,…,em))=T(call/return)+mT(par)+T(F-body)

例：

T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b)

相應(yīng)的匯編程序?yàn)椋?/p>

loadainR1loadbinR2addR2toR1load.cinR2storeR1inR2～～通常取O(1)(2)語(yǔ)句序列

T(s1,s2,…,sk)=max{T(s1),T(s2),…,T(sk))(3)條件語(yǔ)句

T(if(B)s1elses2)=T(B)+T(else)+max{T(s1),T(s2)}

通常取T(B)+T(else)=O(1)

T(if(B)s)=O(1)+T(s)(4)Switch語(yǔ)句設(shè)語(yǔ)句sswitch(E){caseE1:S1;…caseEk:Sk;default:Sm}

T(s)=T(E)+∑T(Ei)+max{T(s1),…,T(sk),T(sm)}

O(1)ki=1(5)for語(yǔ)句

T(for(i=1;i<=n;i++)s)=∑(T(s)+T(i=1)+T(i<=n)+T(i++)+T(for))O(1)(6)while語(yǔ)句

while(B)si=0;while(B){s;i++}

設(shè)RT0表示某一次循環(huán)開始執(zhí)行時(shí)的絕對(duì)時(shí)間關(guān)于循環(huán)的定時(shí)不變式RT為

RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j))

其中：T(while)代表測(cè)試循環(huán)終止條件所耗時(shí)間

T(j)代表跳回循環(huán)頭所耗時(shí)間可簡(jiǎn)化成：T(j)=T(while)

T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while)(7)函數(shù)調(diào)用非遞歸調(diào)用：∑被調(diào)用子函數(shù)運(yùn)行時(shí)間遞歸調(diào)用：求解遞歸方程(8)goto語(yǔ)句

goto語(yǔ)句破壞了程序結(jié)構(gòu)一般對(duì)goto語(yǔ)句限制使用對(duì)有條件的goto轉(zhuǎn)移可忽略不計(jì)舉例：

①s=0;→f(n)=1;T1(n)=O(f(n))=O(1)常量階

②for(i=1;i<=n;++i){++x;s+=x;}→f(n)=3n+1;T2(n)=O(f(n))=O(n)線性階

③for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}→f(n)=3n2+2n+1;T3(n)=O(f(n))=O(n2)平方階

④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];}→f(n)=2n3+3n2+2n+1;T4(n)=O(f(n))=O(n3)立方階VoidBUBBLE(A)int

A[n];{int

I,j,temp;

for(i=0;i<n-1;i++)

for(j=n-1;j>=i+1;j--)O(