數(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)成績占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ù)庫系統(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ù)庫系統(tǒng)Linux操作系統(tǒng)*程序設(shè)計(jì)語言用戶界面設(shè)計(jì)面向?qū)ο蠹夹g(shù)與UMLJava語言程序設(shè)計(jì)實(shí)踐面向服務(wù)的計(jì)算技術(shù).NetC++語言J2EE軟件開發(fā)實(shí)踐軟件外包開發(fā)技術(shù)*英語限選軍訓(xùn)大學(xué)外語體育政治大學(xué)外語體育馬哲英語限選體育英語限選體育英語口語英語限選英語口語工科數(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ā)過程管理軟件質(zhì)量保證與測(cè)試軟件工程綜合課程設(shè)計(jì)計(jì)算機(jī)職業(yè)道德市場營銷知識(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++語言描述（影印版）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ù)來表示,

研究信息表示和信息處理?！魯?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í)語言中變量的取值范圍和允許的操作

什么是數(shù)據(jù)？大數(shù)據(jù)(bigdata)大數(shù)據(jù)可分成：大數(shù)據(jù)技術(shù)大數(shù)據(jù)工程：大數(shù)據(jù)工程指大數(shù)據(jù)的規(guī)劃建設(shè)運(yùn)營管理的系統(tǒng)工程；大數(shù)據(jù)科學(xué)：大數(shù)據(jù)科學(xué)關(guān)注大數(shù)據(jù)網(wǎng)絡(luò)發(fā)展和運(yùn)營過程中發(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)控過程中，可能有用的數(shù)據(jù)

僅僅有一兩秒。—Velocity：處理速度快，1秒定律。第一，大數(shù)據(jù)的基本概念第二，大數(shù)據(jù)計(jì)算機(jī)其挑戰(zhàn)第三，研究問題與部分解大數(shù)據(jù)無處不在：因特網(wǎng)有很多的大數(shù)據(jù)，在科學(xué)研究領(lǐng)域、醫(yī)療領(lǐng)域、商業(yè)領(lǐng)域、制造業(yè)、智慧城市都有大量的數(shù)據(jù)。全世界的感知數(shù)據(jù)增長率是每年58%全世界擁有的存儲(chǔ)能力或者是存儲(chǔ)總量的增長率是每年只有40%2007年，全世界的感知數(shù)據(jù)已經(jīng)超過了全世界所擁有的存儲(chǔ)器的容量2010年，全世界的感知數(shù)據(jù)是1.25千萬PB2011年產(chǎn)生的感知數(shù)據(jù)已經(jīng)二倍于我們?nèi)祟愃鶕碛械拇鎯?chǔ)器的容量結(jié)論：大數(shù)據(jù)無處不在，數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超出了現(xiàn)有的存儲(chǔ)能力大數(shù)據(jù)的輸入是大數(shù)據(jù)D，問題的解是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)有向圖、無向圖等①②③⑤

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

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

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

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

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

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

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

變化。多分析一步，增加64萬億個(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)過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億步?！吧駚碇帧?.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ī)解題過程：問題→數(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ù)值問題■FORTRAN,ALGOL等高級(jí)語言是以程序?yàn)橹行膫?cè)重于解決數(shù)值問題■LISP,SONBOL表或串處理語言是以數(shù)據(jù)為中心側(cè)重于解決非數(shù)值問題●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語言開始逐漸形成二者結(jié)合知識(shí)結(jié)構(gòu)1.3抽象數(shù)據(jù)型AbstractDataTypes（ADT）

●軟件系統(tǒng)由數(shù)據(jù)結(jié)構(gòu)、操作過程和控制機(jī)能三者組成，軟件設(shè)計(jì)是對(duì)三者的抽象過程，即數(shù)據(jù)抽象、過程抽象和控制抽象。[定義]：抽象數(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的型為LIST線性表實(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）舉例㈠定義任意線性表類型為LIST，其中元素類型為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ì)語言，可以用任意的語言來描述規(guī)格描述的兩個(gè)方面:語法和語義△語法：給出操作的名稱、I/O參數(shù)的數(shù)目和類型△語義：由一組等式組成，定義各種操作的功能及相互間的關(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ù)型——棧語法：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ù)型——棧語義：

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

②有盡可能好的通用性

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

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

①限制使用GOTO語句（基于三種基本結(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ì)問題環(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ù)雜性問題的最重要的辦法是抽象，對(duì)一個(gè)復(fù)雜問題，不應(yīng)馬上用計(jì)算機(jī)指令、數(shù)字與邏輯字來表示，而應(yīng)該用較為自然的抽象語句來表示，從而得出抽象程序。抽象程序?qū)Τ橄蟮臄?shù)據(jù)進(jìn)行某些特定的運(yùn)算并用某些合適的記號(hào)（可能是自然語言）來表示。對(duì)抽象程序作進(jìn)一步的分解，并進(jìn)入下一層的抽象，這樣的精細(xì)化過程一直進(jìn)行下去，直到程序能被計(jì)算機(jī)接受為止。此時(shí)的程序可能是某種高級(jí)語言或機(jī)器指令書寫的?！薄狽.wirth基于數(shù)據(jù)結(jié)構(gòu)的jackson設(shè)計(jì)方法：①研究問題環(huán)境，確定要處理的數(shù)據(jù)結(jié)構(gòu)②基于數(shù)據(jù)結(jié)構(gòu)，形成程序結(jié)構(gòu)（骨架）③用初等操作來定義要完成的任務(wù)，并分配初等操作“從上到下，逐步求精”算法（Algorithm）：是對(duì)特定問題求解步驟的一種描述，它是指令（規(guī)則）的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說,就是計(jì)算機(jī)解題的過程。在這個(gè)過程中，無論是形成解題思路還是編寫程序,都是在實(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ù)原和化簡的規(guī)則》)；1.5算法描述與算法分析資料：Algorithm與Logarithm這個(gè)詞一直到1957年之前在Webster'sNewWorldDictionary(《韋氏新世界詞典》)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術(shù))，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程。在中世紀(jì)時(shí)，珠算家用算盤進(jìn)行計(jì)算，而算術(shù)家用算術(shù)進(jìn)行計(jì)算。中世紀(jì)之后，對(duì)這個(gè)詞的起源已經(jīng)拿不準(zhǔn)了，早期的語言學(xué)家試圖推斷它的來歷，認(rèn)為它是從把a(bǔ)lgiros(費(fèi)力的)+arithmos(數(shù)字)組合起來派生而成的，但另一些人則不同意這種說法，認(rèn)為這個(gè)詞是從“喀斯迪爾國王Algor”派生而來的。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實(shí)起源：它來源于著名的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ù)原和化簡的規(guī)則》)；另一個(gè)詞，“algebra”(代數(shù))，是從他的書的標(biāo)題引出來的，盡管這本書實(shí)際上根本不是講代數(shù)的。逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個(gè)詞是由于同arithmetic(算術(shù))相混淆而形成的錯(cuò)拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學(xué)詞典Vollstandiges

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

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

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

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

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

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

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

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

①正確性，算法能滿足具體問題的需求

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

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

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

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

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

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

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

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

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

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

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

③new和delete

④引入引用類型

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

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

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

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

T（n）=O（f（n））它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同。漸近空間復(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á)式和賦值語句

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)語句序列

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

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語句設(shè)語句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語句

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

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í)間可簡化成：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語句

goto語句破壞了程序結(jié)構(gòu)一般對(duì)goto語句限制使用對(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(