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

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

andAlgorithm本章主要內(nèi)容1.1數(shù)據(jù)結(jié)構(gòu)研究對象1.2數(shù)據(jù)結(jié)構(gòu)發(fā)展概況1.3抽象數(shù)據(jù)型(ADT)1.4數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計1.5算法描述與算法分析1.1數(shù)據(jù)結(jié)構(gòu)研究對象◆計算機科學：信息在計算機內(nèi)使用數(shù)據(jù)來表示,

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

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

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

用的數(shù)據(jù)僅僅有一兩秒?！猇elocity：處理速度快，1秒定律。即要在秒級時間范圍內(nèi)給出

分析結(jié)果,超出這個時間,數(shù)據(jù)就失去價值了?！魯?shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素彼此之間抽象的相互關(guān)系，解決數(shù)據(jù)的存儲和組織的方式，不涉及數(shù)據(jù)元素的具體內(nèi)容。描述現(xiàn)實世界事物的數(shù)學模型及其操作在計算機中的表示和實現(xiàn)◆數(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)系，組成整體的各部分的搭配和安排非線性結(jié)構(gòu)O××OO×××O×O××O×O××OO×××OO××O×

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

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

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

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

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

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

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

卡斯帕羅夫:第一次1996年：2月10日—17日，比分2:4，卡斯帕羅夫贏第二次1997年：5月3日—11日，比分3.5:2.5雙方先后共進行6局對弈：第一局：卡斯帕羅夫執(zhí)白先行，經(jīng)過3個多小時的苦戰(zhàn)擊敗

深藍力拔頭籌；第二局：深藍卻以凌厲的攻勢和明顯的優(yōu)勢戰(zhàn)勝卡氏，扳回

一局；第三、第四和第五局：雙方下得異常激烈，鏖戰(zhàn)數(shù)小時，

平局；第六局：深藍執(zhí)白先行，一路強攻，僅用一個多小時，雙方

僅走了19步，就讓卡氏俯首稱臣，取得了決定性的

勝利。IBM“深藍”--棋王卡斯帕羅夫卡斯帕羅夫深藍身高5英尺10英寸6英尺5英寸體重176磅1.27噸年齡34歲4歲行棋速度2步/每秒2億步/每秒-1980年，臺灣大學電機系畢業(yè);-獲得了電子工程學士學位;-美國卡內(nèi)基·梅隆大學博士;-曾在IBM工作;-現(xiàn)在微軟亞洲研究院?？ㄋ古亮_夫:他在觀察電腦下棋時感覺電腦的決定有智慧及創(chuàng)意，是他所不能理解的。他亦認為電腦在棋局中可能有人類的幫助，因此要求重賽。IBM:拒絕，并把深藍退役。2003年紀錄片“游戲結(jié)束：卡斯巴羅夫與電腦”(GameOver:KasparovandtheMachine)。許峰雄深藍-1996年，美國IBM公司；-基于RS/6000

SP設(shè)計；-AIX操作系統(tǒng)；-重1270公斤，32個微處理器；-每秒鐘可以計算2億步?！吧駚碇卑柗▏澹ˋlphaGo）是一款圍棋人工智能程序，由英國倫敦的谷歌（Google）旗下DeepMind公司的戴維·西爾弗、艾佳·黃和戴密斯·哈薩比斯與他們的團隊開發(fā)，這個程序利用“價值網(wǎng)絡(luò)”計算局面，用“策略網(wǎng)絡(luò)”選擇下子。2015年10月阿爾法圍棋以5:0完勝歐洲圍棋冠軍、職業(yè)二段選手樊麾；2016年3月對戰(zhàn)世界圍棋冠軍、職業(yè)九段選手李世石，并以4:1的總比分獲勝。

面對AlphaGo碾壓式的實力，19歲的“大魔王”柯杰：“AlphaGo實在下得太好。我擔心的每一步棋他都會下，還下出我想不到的棋，我仔細慢慢思索，發(fā)現(xiàn)原來又是一步好棋。我只能猜出AlphaGo一半的棋，另一半我猜不到，就是差距，我和他差距實在太大?！?017年5月23、25、27日

AlphaGo設(shè)計者：戴維·西爾弗（DavidSilver），劍橋大學計算機科學學士，碩士，加拿大阿爾伯塔大學計算機科學博士?，F(xiàn)為倫敦大學學院講師及GoogleDeepMind研究員。艾佳·黃（黃士杰，AjaHuang），臺灣交通大學計算機科學學士，臺灣師范大學計算機科學碩士和博士，加拿大阿爾伯塔大學計算機科學博士后?，F(xiàn)為GoogleDeepMind研究員。AlphaGo使用1820多塊CPU及280多塊GPU（GraphicProcessingUnit），據(jù)說，這次圍棋對戰(zhàn)分析只用了服務(wù)器總的百分之三十資源，其余的在空閑。谷歌AlphaGo計算能力超IBM深藍2.5--3萬倍！經(jīng)過短短3天的自我訓練，AlphaGoZero就強勢打敗了此前戰(zhàn)勝李世石的舊版AlphaGo，戰(zhàn)績是100:0的。經(jīng)過40天的自我訓練，AlphaGoZero又打敗了AlphaGoMaster版本?！癕aster”曾擊敗過世界頂尖的圍棋選手，甚至包括世界排名第一的柯潔。Master補充1：適用于并行計算——并發(fā)數(shù)據(jù)結(jié)構(gòu)或多線程數(shù)據(jù)結(jié)構(gòu)設(shè)計并發(fā)數(shù)據(jù)結(jié)構(gòu)（互斥鎖）設(shè)計不使用互斥鎖的并發(fā)數(shù)據(jù)結(jié)構(gòu)以隊列為例：并發(fā)隊列并發(fā)阻塞隊列有超時限制的并發(fā)阻塞隊列有大小限制的并發(fā)阻塞隊列有操作限制的并發(fā)阻塞隊列如何設(shè)計支持并發(fā)訪問的數(shù)據(jù)結(jié)構(gòu)？設(shè)計可以基于互斥鎖，也可以是無鎖的。無論哪種方式，要考慮的問題不僅僅是這些數(shù)據(jù)結(jié)構(gòu)的基本功能—具體來說，必須一直記住線程會爭奪執(zhí)行權(quán)，要考慮線程重新執(zhí)行時如何恢復(fù)操作。試圖從沒有數(shù)據(jù)的隊列讀取數(shù)據(jù)，僅僅會拋出異常并繼續(xù)執(zhí)行。但是，這種做法不總是我們想要的，讀線程很可能希望等待，直到有數(shù)據(jù)時為止。這種隊列稱為阻塞的隊列。補充2：適用于分布式系統(tǒng)——分布式Hash表或者分布式B+樹Hash算法：模N（N為機器數(shù)）Hash或者一致性Hash模N哈希的主要問題：機器上下線時機器數(shù)變化導致所有的數(shù)據(jù)都需要重新分布，一致性Hash用來解決這個問題。分布式Hash存儲系統(tǒng)由于只支持隨機讀取，一般用選擇相對較好的磁盤，分布式B+樹存儲系統(tǒng)同時支持隨機讀取和順序掃描，當用來支持使用模式主要為順序掃描的應(yīng)用時，可以選擇相對較差的磁盤，比如SATA盤。Hash空間組織成一個環(huán)，環(huán)上相鄰節(jié)點包含的數(shù)據(jù)構(gòu)成一個桶；比如Hash空間為A,B,C，那么有[A,B],[B,C],以及[C,A]三個桶；每個桶內(nèi)的數(shù)據(jù)結(jié)構(gòu)為Log-StructuredHashTable；當然，可根據(jù)需要修改每個桶的單機數(shù)據(jù)結(jié)構(gòu)；桶是負載均衡和任務(wù)調(diào)度的基本單元；每個桶存放3個副本。1.1數(shù)據(jù)結(jié)構(gòu)研究對象1、數(shù)據(jù)結(jié)構(gòu)研究方法邏輯結(jié)構(gòu)：對操作對象的一種數(shù)學描述，或從操作對象中抽象出的數(shù)學模型，用以描述數(shù)據(jù)元素之間的邏輯關(guān)系，與存儲方式無關(guān)。物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示或映象，邏輯結(jié)構(gòu)

的存儲方式。又稱存儲結(jié)構(gòu)，分為順序映象和非順序映象；

或稱順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)；計算機解題過程：問題→數(shù)學模型→算法→程序→測試→計算分析數(shù)據(jù)并確定存儲結(jié)構(gòu)輸入到計算機中2、數(shù)據(jù)結(jié)構(gòu)研究的范疇程序設(shè)計：為計算機處理問題編制一組指令集算法：怎么處理的策略數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學模型程序設(shè)計、算法、數(shù)據(jù)結(jié)構(gòu)數(shù)值計算的程序設(shè)計問題：問題算法數(shù)學模型求解一元二次方程？求根公式一組整數(shù)排序“冒泡”方法數(shù)組結(jié)構(gòu)靜力分析計算？線性代數(shù)方程組全球天氣預(yù)報？環(huán)流模式方程非數(shù)值計算的程序設(shè)計問題：問題算法數(shù)學模型求一組整數(shù)的最大值比較兩個數(shù)的大??？計算機對弈對弈的規(guī)則和策略棋子、棋盤的表示足協(xié)的數(shù)據(jù)庫管理什么項目？如何管理？接口？條例？規(guī)則？表格，數(shù)據(jù)庫1.2數(shù)據(jù)結(jié)構(gòu)發(fā)展概況數(shù)據(jù)結(jié)構(gòu)側(cè)重解決非數(shù)值問題FORTRAN,ALGOL等高級語言是以程序為中心側(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)”逐漸開始成為獨立的一門課程；

作為一門專業(yè)基礎(chǔ)課，“數(shù)據(jù)結(jié)構(gòu)”是計算機專業(yè)的核心課程之一，是其他專業(yè)課的基礎(chǔ)。是數(shù)學、硬件和軟件三者的交叉，很受重視。從PASCAL語言開始逐漸形成二者結(jié)合；知識結(jié)構(gòu)《數(shù)據(jù)結(jié)構(gòu)》所處的地位1.3抽象數(shù)據(jù)型AbstractDataTypes（ADT）＊軟件系統(tǒng)由數(shù)據(jù)結(jié)構(gòu)、操作過程和控制機能三者組成，軟件設(shè)計是對三者的抽象過程，即數(shù)據(jù)抽象、過程抽象和控制抽象?！径x】抽象數(shù)據(jù)型是一個數(shù)學模型和在該模型上定義的操作的集合。ADT特點：①降低了軟件設(shè)計的復(fù)雜性；②提高了程序的可讀性和可維護性；③程序的正確性容易保證。抽象：從眾多事物中舍棄個別的、非本質(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線性表實例，x的型為ElementType的元素實例，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ù)學模型【例1-1】定義任意線性表類型為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-2】假設(shè)利用兩個線性表LA和LB分別表示兩個集合，設(shè)計算法求一個新的集合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);}}抽象數(shù)據(jù)型的規(guī)格描述△完整性：反映所定義的抽象數(shù)據(jù)型的全部特征；△統(tǒng)一性：前后協(xié)調(diào)，不自相矛盾；△通用性：適用于盡量廣泛的對象；△不依賴性：不依賴于程序設(shè)計語言，可以用任意的語言來描述；規(guī)格描述的兩個方面:語法和語義△語法：給出操作的名稱、I/O參數(shù)的數(shù)目和類型；△語義：由一組等式組成，定義各種操作的功能及相互間的關(guān)系；例如：抽象數(shù)據(jù)型——棧(Stack)【定義】棧是一個后進先出（LIFO）的線性表，所有插入、刪除操作是在表的一端（棧頂）進行。聚集數(shù)組，鏈表(結(jié)構(gòu)體、記錄)，文件棧(Stack)示意圖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ù)型的實現(xiàn)抽象描述：（高級語言）編寫的程序三條原則：①符合規(guī)格描述的定義；②有盡可能好的通用性；③盡可能獨立于程序的其他部分。多層次抽象技術(shù)自底向上與自頂向下相結(jié)合、由簡單到復(fù)雜1.4數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計Algorithms+DataStructures=Programs算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計《系統(tǒng)程序設(shè)計導論》（《SystematicProgramming：AnIntroduction》，Prentice-Hall，1973；《算法+數(shù)據(jù)結(jié)構(gòu)=程序》（《Algorithms+DataStructures=Programs》，Prentice-Hall，1976）；《算法和數(shù)據(jù)結(jié)構(gòu)》（《AlgorithmsandDataStructures》，Prentice-Hall，1986）；《Modula-2程序設(shè)計》（《ProgramminginModula-2》，Springer，1988，第4版）?！禤ASCAL用戶手冊和報告：ISOPASCAL標準》（《PASCALUserManualandReport：ISOPASCALStandard》，Springer，1991）；《Oberon計劃：操作系統(tǒng)和編譯器的設(shè)計》（《ProjectOberon：theDesignofanOperatingSystemandCompiler》，ACMPr.，1992）；《Oberon程序設(shè)計：超越Pascal和Modula》（《ProgramminginOberon：StepsbeyondPascalandModula》，ACMPr.，1922）；《數(shù)字電路設(shè)計教材》（《DigitalCircuitDesignforComputerScienceStudents：AnIntroductoryTextbook》，Springer，1995）。尼古拉斯·沃斯（NiklausWirth，1934年2月15日）；生于瑞士溫特圖爾，瑞士計算機科學家；蘇黎世工學院獲得學士學位，美國加州大學伯克利分校獲得博士學位；代表性著作有：獲獎：1984年：獲圖靈獎（ACM）；1987年：獲計算機科學教育杰出貢獻獎（ACM）；1983年：EmanualPiore獎（IEEE）；1988年：計算機先驅(qū)獎（IEEE）；1992年：加州大學伯克利分校命名沃斯為“杰出校友”。1984問題解決問題的算法實現(xiàn)算法的程序問題總是先于算法程序設(shè)計的四個里程碑：

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

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

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

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

④主程序員組的組織形式；問題環(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è)計“我們對復(fù)雜性問題的最重要的辦法是抽象，對一個復(fù)雜問題，不應(yīng)馬上用計算機指令、數(shù)字與邏輯字來表示，而應(yīng)該用較為自然的抽象語句來表示，從而得出抽象程序。抽象程序?qū)Τ橄蟮臄?shù)據(jù)進行某些特定的運算并用某些合適的記號(可能是自然語言)來表示?；跀?shù)據(jù)結(jié)構(gòu)的jackson設(shè)計方法：①研究問題環(huán)境，確定要處理的數(shù)據(jù)結(jié)構(gòu)；②基于數(shù)據(jù)結(jié)構(gòu)，形成程序結(jié)構(gòu)（骨架）；③用初等操作來定義要完成的任務(wù)，并分配初等操作?！皬纳系较?，逐步求精”對抽象程序作進一步的分解，并進入下一層的抽象，這樣的精細化過程一直進行下去，直到程序能被計算機接受為止。此時的程序可能是某種高級語言或機器指令書寫的?！薄狽.wirth算法（Algorithm）：是對特定問題求解步驟的一種描述，它是指令（規(guī)則）的有限序列，其中每一條指令表示一個或多個操作。算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則；通俗點說,就是計算機解題的過程；在這個過程中，無論是形成解題思路還是編寫程序,都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。1.5算法描述與算法分析早期的語言學家：algiros(費力的)+arithmos(數(shù)字)組合派生而成，但另一些人認為這個詞是從“喀斯迪爾國王Algor”派生而來的；數(shù)學史學家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實起源：它來源于著名的PersianTextbook(《波斯教科書》)的作者的名字AbuJa‘farMohammedibnM?saal-Khowarizm（約公元前825年）意思是“Ja’far的父親，Mohammed和M?sa的兒子，Khowarizm的本地人”。Khowarizm是前蘇聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowarizm寫了著名的書Kitabaljabrw‘a(chǎn)l-muqabala(《復(fù)原和化簡的規(guī)則》)；另一個詞，“algebra”(代數(shù))，是從他的書的標題引出來的；牛津英語字典:這個詞是由于同arithmetic(算術(shù))相混淆而形成的錯拼詞。由algorism又變成algorithm；德文數(shù)學詞典VollstandigesMathematischesLexicon(《數(shù)學大全辭典》)，給出了Algorithmus(算法)一詞的如下定義：“在這個名稱之下，組合了四種類型的算術(shù)計算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmusinfinitesimalis(無限小方法)，在當時就用來表示Leibnitz(萊布尼茲)所發(fā)明的以無限小量進行計算的微積分方法；1950年左右，algorithm一詞經(jīng)常地同歐幾里德算法(Euclid'salgorithm)聯(lián)系在一起。這個算法就是在歐幾里德的《幾何原本》中所闡述的求兩個數(shù)的最大公約數(shù)的過程(即輾轉(zhuǎn)相除法)。資料：Algorithm與Logarithm經(jīng)過月數(shù)兔子對數(shù)001121324355687138219341055118912144(1175-1250）意大利數(shù)學家從Fibonacci數(shù)列開始……,神奇的數(shù)列！斐波那契在《算盤書》中提出了一個有趣的兔子問題：一般而言，兔子在出生兩個月后，就有繁殖能力，1對兔子每個月能生出1對小兔子來。如果所有兔都不死，那么1年以后可以繁殖多少對兔子？我們不妨拿新出生的1對小兔子分析一下：第1個月小兔子沒有繁殖能力，所以還是1對；2個月后，生下1對小兔總數(shù)共有2對；3個月以后，老兔子又生下1對，因為小兔子還沒有繁殖能力，所以一共是3對；…….

12個月以后呢？Fibonacci:0,1,1,2,3,5,8,13,21,34,55,89,……….0如果n=01如果n=1Fn-1+Fn-2

如果n>1Fibonacci數(shù)列的生成規(guī)則：Fn=Fn≈20.694n,Fibonacci數(shù)增長的速度幾乎與2的冪增長的速度相當!F30超過了100萬，F(xiàn)100已經(jīng)達到21位數(shù)字！F200是多少？誰能告訴Fibonacci?Longintfib1(intn){if(n==0)return(0);if(n==1)return(1);return(fib1(n-1)+fib(n-2);}fib1(200)執(zhí)行的基本操作次數(shù):T(200)=T(199)+T(198)+3>=2138以每秒33.86千萬億次的計算機測算Fib1(200)的計算時間>=282秒另外一個計算方法：longintfib2(intn){longintF[200],i;if(n==0)return(0);F[0]=0；F[1]=1;for(i=2;i<=200;i++)F[i]=F[i-1]+F[i-2];return(F[200]);}Fib2(n)執(zhí)行的基本操作次數(shù)T(n)是關(guān)于n的線性函數(shù)!T(n)=O(f(n))=O(n)

這僅是以加法為基本操作，你發(fā)現(xiàn)新的問題了嗎？計算F200的時間>1.11*256年Fn≈20.694n≈(1.6)n,計算Fn+1的時間是計算Fn的1.6倍，F(xiàn)n+1=1.6Fn摩爾定律(Moore’slow)：計算機的運算速度每年增長約1.6倍?！吧裢ぬ狻睋魯〉氖前哉及袷?年的“天河2號”?！吧裢ぬ狻边\算速度達到93petaflop（每秒運算一千萬億次），理論最高速達125.4petaflops。這一數(shù)值約為“天河2號”的兩倍。2016年6月20日德國法蘭克福國際超級計算機大會（ISC）公布了新一期世界計算機500強榜單，我國最新的超級計算機“神威·太湖之光”登頂。最受關(guān)注的是，“神威·太湖之光”實現(xiàn)了核心處理器的全國產(chǎn)化。超算2018新一期全球超級計算機500強榜單2018年6月25日發(fā)布，美國超級計算機“頂點”超過中國的“神威·太湖之光”名列第一，這是美國超級計算機多年后重回榜首。美國能源部下屬橡樹嶺國家實驗室的超算“頂點”，浮點運算速度為每秒12.23億億次，峰值接近每秒18.77億億次。排名第二的是曾4次蟬聯(lián)冠軍的中國超算“神威·太湖之光”，其浮點運算速度沒有變化，仍維持在每秒9.3億億次。隨后排在第三至五位的超算依次是美國能源部下屬勞倫斯利弗莫爾國家實驗室的“山脊”、中國超算“天河二號”、日本超算“人工智能橋接云基礎(chǔ)設(shè)施”（ABCI）。

5月在天津舉辦的第二屆世界智能大會上，中國國家超算天津中心對外展示了我國新一代百億億次超級計算機“天河三號”原型機，有望在2020年研制成功并重回超算榜首。遞歸技術(shù)：最常用的算法設(shè)計思想，體現(xiàn)于許多優(yōu)秀算法之中；分治法：分而制之的算法思想，體現(xiàn)了一分為二的哲學思想；模擬法：用計算機模擬實際場景，經(jīng)常用于與概率有關(guān)的問題；貪心算法：采用貪心策略的算法設(shè)計；狀態(tài)空間搜索法：被稱為“萬能算法”的算法設(shè)計策略；隨機算法：利用隨機選擇自適應(yīng)地決定優(yōu)先搜索的方向；動態(tài)規(guī)劃：常用的最優(yōu)化問題解決方法。常見的計算機算法：“好”的算法的標準：①正確性，算法能滿足具體問題的需求；②可讀性，首先方便閱讀與交流，其次才是機器執(zhí)行；③健壯性，輸入錯誤時，能作出反應(yīng)，避免異常出錯；④效率與低存儲量要求。算法的特征：

①有窮性、②確定性、③輸入、④輸出、⑤能行性算法效率衡量和準則：①事后統(tǒng)計法

必須執(zhí)行程序，

可能有其他因素掩蓋算法的本質(zhì)；②事前分析估算法對算法“正確性”的要求：

①不含語法錯誤；

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

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

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

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

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

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

③new和delete；

④引入引用類型；

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

①算法實現(xiàn)后所消耗的時間**；②算法實現(xiàn)后所占存儲空間的大小*；③算法是否易讀、易移植等等其它問題。影響時間特性的五個因素：①算法選用的策略；

②程序運行時輸入數(shù)據(jù)的總量，即問題的規(guī)模；③對源程序編譯所需的時間，產(chǎn)生機器代碼的質(zhì)量；④計算機執(zhí)行每條指令所需的時間/速度；⑤程序中指令重復(fù)執(zhí)行的次數(shù)*?！径x】語句頻度：語句重復(fù)執(zhí)行的次數(shù)。程序運行時間漸近時間復(fù)雜度（時間復(fù)雜度）T（n）

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

T（n）=O（f（n））它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同。漸近空間復(fù)雜度（空間復(fù)雜度）S（n）S（n）=O（g（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))程序運行時間比較T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△T(n)設(shè)：T(x)：取變量或常量x之值所消耗時間T(.V)：取變量V之地址所消耗的時間T(=)：賦值所消耗時間T(θ)：執(zhí)行基本運算θ所耗時間T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時間T(par)：將參數(shù)par傳給函數(shù)所消耗時間～(1)表達式和賦值語句

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)的匯編程序為：

loadainR1loadbinR2addR2toR1loadcinR2storeR1inR2～～通常取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í)行時的絕對時間關(guān)于循環(huán)的定時不變式RT為

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

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

T(j)代表跳回循環(huá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ù)運行時間遞歸調(diào)用：求解遞歸方程(8)goto語句

goto語句破壞了程序結(jié)構(gòu)一般對goto語句限制使用對有條件的goto轉(zhuǎn)移可忽略不計【例1-3】

①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))