數(shù)據(jù)結(jié)構(gòu)與算法第一張清華大學(xué)出版社趙玉蘭

劉詠梅cslym@內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院315數(shù)據(jù)結(jié)構(gòu)與算法

DATASTRUCTURE

ANDARITHMETIC數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第1頁!課程介紹課程性質(zhì)計(jì)算機(jī)專業(yè)的課程分為公共基礎(chǔ)課專業(yè)基礎(chǔ)課專業(yè)方向課專業(yè)選修課屬于專業(yè)基礎(chǔ)課考研的必考科目計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考專業(yè)基礎(chǔ)綜合共150分，其中《數(shù)據(jù)結(jié)構(gòu)》占45分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第2頁!課程介紹在教學(xué)計(jì)劃中的地位：核心課程前導(dǎo)課程高等數(shù)學(xué)離散數(shù)學(xué)程序設(shè)計(jì)語言后續(xù)課程操作系統(tǒng)編譯數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第3頁!課程介紹教學(xué)內(nèi)容第3單元常用數(shù)據(jù)處理技術(shù)數(shù)據(jù)結(jié)構(gòu)的基本概念算法的基本概念第1單元基本概念線性表樹和二叉樹圖特殊線性表廣義線性表第2單元基本數(shù)據(jù)結(jié)構(gòu)排序技術(shù)索引技術(shù)查找技術(shù)集合數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第4頁!課程介紹成績組成總成績＝平時(shí)成績×30％＋期末考試成績×70％平時(shí)成績包括作業(yè)成績和上機(jī)成績數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第5頁!第1章概述1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展1.2數(shù)據(jù)結(jié)構(gòu)1.3數(shù)據(jù)的邏輯結(jié)構(gòu)1.4抽象數(shù)據(jù)類型1.5數(shù)據(jù)的存儲結(jié)構(gòu)1.6算法與算法分析1.7總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第6頁!1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展程序設(shè)計(jì)的發(fā)展階段無結(jié)構(gòu)階段應(yīng)用領(lǐng)域：科學(xué)計(jì)算處理的數(shù)據(jù)：數(shù)值型數(shù)據(jù)數(shù)據(jù)之間的關(guān)系：數(shù)學(xué)方程或數(shù)學(xué)模型例方程組求解定積分在這一階段，數(shù)據(jù)結(jié)構(gòu)還未形成一門系統(tǒng)的學(xué)科，而是零星地分布在程序設(shè)計(jì)、圖論、集合、代數(shù)、操作系統(tǒng)和編譯原理等課程中。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第7頁!1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展面向?qū)ο箅A段應(yīng)用領(lǐng)域：更多地應(yīng)用于非數(shù)值處理處理的數(shù)據(jù)：更多地處理非數(shù)值型數(shù)據(jù)數(shù)據(jù)之間的關(guān)系：數(shù)據(jù)結(jié)構(gòu)發(fā)展到面向?qū)ο箅A段（數(shù)據(jù)結(jié)構(gòu)＋算法）＝程序類和數(shù)據(jù)結(jié)構(gòu)之間的對應(yīng)關(guān)系類屬性方法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)之間的關(guān)系基本操作對應(yīng)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第8頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究對象用計(jì)算機(jī)求解問題的一般過程具體問題建立模型設(shè)計(jì)算法編制計(jì)算機(jī)程序問題分為兩類數(shù)值問題非數(shù)值問題數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第9頁!1.2數(shù)據(jù)結(jié)構(gòu)非數(shù)值問題例1電話號碼簿黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院4992930黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院4992930黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院4992930黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院49929306845678是誰的電話？太難找了！數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第10頁!1.2數(shù)據(jù)結(jié)構(gòu)改變結(jié)構(gòu)：按電話號碼的大小排列黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院4992930黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院4992930黨政機(jī)關(guān)黨委總機(jī)4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學(xué)校務(wù)辦公室4991234計(jì)算機(jī)學(xué)院4992930110……...匪警119………火警120………急救1234567….…….6845678….Tom………6845678是老朋友Tom的電話，太容易找了！數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第11頁!1.2數(shù)據(jù)結(jié)構(gòu)例3人機(jī)對弈問題——樹結(jié)構(gòu)…………..……..………...……數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第12頁!1.2數(shù)據(jù)結(jié)構(gòu)總結(jié)非數(shù)值問題建立的模型是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)，而不是數(shù)學(xué)方程非數(shù)值問題求解的核心是數(shù)據(jù)處理，而不是數(shù)值計(jì)算數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第13頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素（DataElement）（數(shù)據(jù)成員）：數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。數(shù)據(jù)項(xiàng)（DataItem）：組成數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第14頁!1.2數(shù)據(jù)結(jié)構(gòu)例2學(xué)籍管理問題每一行是一個(gè)數(shù)據(jù)元素每一列是一個(gè)數(shù)據(jù)項(xiàng)學(xué)生數(shù)據(jù)元素的集合是一個(gè)數(shù)據(jù)對象姓名學(xué)號性別年齡民族系專業(yè)入學(xué)時(shí)間王小林060631男18漢族計(jì)算機(jī)計(jì)算機(jī)科學(xué)2006.9陳紅060632女20蒙族計(jì)算機(jī)計(jì)算機(jī)應(yīng)用2006.9劉建平060633男19回族計(jì)算機(jī)電子商務(wù)2006.9……..……..…….…….……………….數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第15頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)按照某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲方法把它存儲在計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第16頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)預(yù)備知識偶對在數(shù)學(xué)中，用來表示兩個(gè)事物之間所具有的固定關(guān)系的方法，叫偶對分類無序偶對兩個(gè)事物之間的關(guān)系沒有次序之分表示：(a,b)有序偶對兩個(gè)事物之間的關(guān)系有次序之分表示：<a,b>abab數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第17頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)二元關(guān)系（DualityRelationship）R是集合A上的二元關(guān)系：RAA數(shù)據(jù)的邏輯結(jié)構(gòu)由數(shù)據(jù)元素集及其邏輯關(guān)系組成，可形式地描述為：Data_Structure=（D,R）其中：D是數(shù)據(jù)元素的有限集合；R是D上的有限關(guān)系集合。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第18頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)（LinearStructure）LS=(D,R)

D={d1,d2,…,dn}R={<di,di+1>|i=1,2,3,…,n-1}例4DS=(D,R1)

D={d1,d2,d3,d4,d5,d6}R1={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>,<d5,d6>}d1d2d3d4d5d6僅有一個(gè)開始結(jié)點(diǎn)，僅有一個(gè)終端結(jié)點(diǎn)其它都是內(nèi)部結(jié)點(diǎn)，且都有且僅有一個(gè)直接前驅(qū)、一個(gè)直接后繼數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第19頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)樹形結(jié)構(gòu)例6DS=(D,R3)

D={d1,d2,d3,d4,d5,d6,d7}R3={<d1,d2>,<d1,d3>,<d3,d7>,<d2,d4>,<d2,d5>,<d2,d6>}d4d1d2d3d5d6

d7

有且僅有一個(gè)根結(jié)點(diǎn)其它結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)對于非根結(jié)點(diǎn)都存在從根到該結(jié)點(diǎn)的一條路徑結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第20頁!1.4抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTypes，ADT）面向?qū)ο蠹夹g(shù)核心概念面向?qū)ο蟪绦蛟O(shè)計(jì)的基礎(chǔ)（C++，Java，……）抽象層次高，模塊復(fù)用度高——使用ADT有極大的優(yōu)勢數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第21頁!1.4抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTypes，ADT）一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作的總稱抽象數(shù)據(jù)類型與數(shù)據(jù)類型的區(qū)別數(shù)據(jù)類型僅局限于計(jì)算機(jī)（高級程序設(shè)計(jì)語言）中定義并實(shí)現(xiàn)了的數(shù)據(jù)類型抽象數(shù)據(jù)類型還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型關(guān)鍵使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲方式定義它的人同樣不必要關(guān)心它如何存儲數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第22頁!1.4抽象數(shù)據(jù)類型例8自然數(shù)的抽象數(shù)據(jù)類型定義ADT

NaturalNumber

{

Data：一個(gè)整數(shù)的有序子集合，它開始于0，結(jié)束于機(jī)器能表示的最大整數(shù)（MaxInt）。

Operations：對于所有的x,yNaturalNumber；False,TrueBoolean，+、-、<、==、=等都是可用的服務(wù)。

Zero()：NaturalNumber

返回自然數(shù)0

IsZero(x):Boolean

if(x==0)返回Trueelse返回False數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第23頁!1.5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)（StoreStructure）數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示面向計(jì)算機(jī)，面向具體實(shí)現(xiàn)分類順序存儲結(jié)構(gòu)（SequentialStoreStructure）鏈?zhǔn)酱鎯Y(jié)構(gòu)（LinkedStoreStructure）數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第24頁!1.5數(shù)據(jù)的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲空間不連續(xù)保持了邏輯關(guān)系數(shù)據(jù)元素的存儲位置e0b1040a1026d1024c1034102410261028103010321034103610381040abcde不考慮具體地址，抽象為數(shù)據(jù)元素指針結(jié)點(diǎn)（node）：存儲一個(gè)數(shù)據(jù)元素及附加信息的存儲空間指針（pointer）：存儲地址

數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第25頁!1.5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的機(jī)外表示，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的機(jī)內(nèi)表示一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲數(shù)據(jù)結(jié)構(gòu)的基本操作是定義于邏輯結(jié)構(gòu)，實(shí)現(xiàn)于存儲結(jié)構(gòu)采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第26頁!1.6算法與算法分析可行性（有效性）算法中的所有操作都可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。輸入算法運(yùn)行過程中從外界給定的數(shù)據(jù)；一個(gè)算法有0個(gè)或多個(gè)輸入數(shù)據(jù)。輸出對輸入數(shù)據(jù)加工后的結(jié)果的輸出；一個(gè)算法至少有1個(gè)輸出數(shù)據(jù)。（必須有輸出）數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第27頁!1.6算法與算法分析評價(jià)算法“好壞”的幾個(gè)標(biāo)準(zhǔn)算法的正確性算法的效率占用空間量簡單性和清晰性最優(yōu)性數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第28頁!1.6算法與算法分析簡單性（Simplicity）簡單的算法的優(yōu)點(diǎn)易于驗(yàn)證正確性易于實(shí)現(xiàn)（編寫程序）易于調(diào)試、修改設(shè)計(jì)算法時(shí)，也需要權(quán)衡簡單性和時(shí)間、空間復(fù)雜度之間的關(guān)系通常方法越直接、越簡單，算法的效率越低數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第29頁!1.6算法與算法分析算法性能分析和度量問題的提出計(jì)算機(jī)的所有應(yīng)用問題，包括計(jì)算機(jī)自身的發(fā)展，都是圍繞著“時(shí)間——速度”這一中心進(jìn)行的。算法的效率（算法的工作量）指算法的執(zhí)行時(shí)間效率越高，工作量越小，執(zhí)行時(shí)間越短對給定的問題設(shè)計(jì)出多種算法時(shí)，如何選擇其中效率高的算法？數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第30頁!1.6算法與算法分析度量算法效率的方法之一——事后測算用源程序分別實(shí)現(xiàn)這些算法，然后輸入適當(dāng)?shù)臄?shù)據(jù)運(yùn)行，測算不同算法花費(fèi)的時(shí)間。缺點(diǎn)編寫多個(gè)程序并進(jìn)行測算，需要花費(fèi)很多的時(shí)間和精力；測試數(shù)據(jù)的選擇可能對其中的某個(gè)算法有利；實(shí)驗(yàn)結(jié)果受運(yùn)行環(huán)境、編譯器、可用存儲空間大小等的影響，有時(shí)容易掩蓋算法本身的優(yōu)劣；即使其中較好的那種算法也超出了你預(yù)算的開銷。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第31頁!1.6算法與算法分析時(shí)間復(fù)雜度（TimeComplexity）例11for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)

x++;count=x; 常規(guī)思維：用日常生活中的時(shí)間來度量算法的執(zhí)行時(shí)間＝∑每條語句執(zhí)行時(shí)間每條語句執(zhí)行時(shí)間＝執(zhí)行次數(shù)×執(zhí)行一次的時(shí)間每條語句執(zhí)行一次的時(shí)間取決于指令系統(tǒng)、編譯產(chǎn)生的代碼質(zhì)量等軟硬件因素

——不公平、計(jì)算繁瑣數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第32頁!1.6算法與算法分析算法的執(zhí)行時(shí)間＝基本語句的執(zhí)行次數(shù)對不同的問題，其求解算法的基本語句是不同的基本語句的執(zhí)行次數(shù)與輸入尺寸有關(guān)輸入尺寸：指輸入量的多少，可從問題描述中得到問題基本語句輸入尺寸在數(shù)組中查找元素x元素比較元素個(gè)數(shù)兩實(shí)數(shù)矩陣相乘加、乘階數(shù)排序 元素比較、移動元素個(gè)數(shù)求多項(xiàng)式P(x)的值加、乘階數(shù)循環(huán) 循環(huán)體數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第33頁!1.6算法與算法分析大O表示法定義：若存在兩個(gè)正常數(shù)c和n0，對于任意n>n0，有|T(n)|c|f(n)|，則稱T(n)在集合O(f(n))中。大O表示法用于描述某一算法的上限，即當(dāng)輸入尺寸為n時(shí)，一種算法所消耗的某種資源（通常是時(shí)間）的最大值。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第34頁!1.6算法與算法分析應(yīng)用規(guī)則加法規(guī)則－－針對并列程序段T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))乘法規(guī)則－－針對嵌套程序段T(n,m)=T1(n)T2(m)=O(f(n)g(m))數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第35頁!1.6算法與算法分析測試題voidexample(floatx[][],intm,intn,intk){floatsum[];for(inti=0;i<m;i++){//x[][]中各行數(shù)據(jù)累加

sum[i]=0.0;for(intj=0;j<n;j++)sum[i]+=x[i][j];

}

for(i=0;i<m;i++)//打印各行數(shù)據(jù)和cout<<“Line”<<i<<“:”<<sum[i]<<endl; }時(shí)間復(fù)雜度為O(max(mn,m))=O(mn)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第36頁!1.6算法與算法分析舊機(jī)器：1小時(shí)可完成10000個(gè)基本操作新機(jī)器：執(zhí)行速度是舊機(jī)器的10倍T(n)：算法的時(shí)間復(fù)雜度n：舊機(jī)器一小時(shí)能完成的輸入尺寸n’：新機(jī)器一小時(shí)能完成的輸入尺寸增長率高的算法從機(jī)器升級中得益較少！數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第37頁!1.6算法與算法分析基本語句：元素比較執(zhí)行次數(shù)：取決于被查元素在數(shù)組中的位置最好情況：數(shù)組中個(gè)元素就是k，算法只需比較1次。最壞情況:數(shù)組中最后一個(gè)元素是k，算法需要比較n次。平均情況：查找到數(shù)組一半時(shí)找到k，比較次數(shù)n/2次。intFind(intA[],intn,intk){for(inti=0;i<n;i++)if(A[i]==k)break;returni;}數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第38頁!1.6算法與算法分析最壞情況下的時(shí)間復(fù)雜度（Worst-caseComplexity）定義為

其中：Dn是問題的所有尺寸為n的輸入集；

I是Dn的元素；

t(I)是算法對輸入I所做的工作量。平均情況下的時(shí)間復(fù)雜度（AverageComplexity）定義為

其中：Pr(I)是輸入元素I出現(xiàn)的概率。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第39頁!1.6算法與算法分析時(shí)間/空間權(quán)衡原則（time/spacetradeoff）犧牲空間或其它資源都可以減少時(shí)間代價(jià)，反之亦然例如：程序?qū)π畔⒌膲嚎s或加密后，可以節(jié)省存儲空間，然而解壓縮和解密的過程又需要額外的時(shí)間代價(jià)。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第40頁!1.6算法與算法分析用自然語言描述算法①輸入m和n；②求m除以n的余數(shù)r；③若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長、二義性使用方法：粗線條描述算法思想注意事項(xiàng)：避免寫成自然段數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第41頁!1.6算法與算法分析用程序設(shè)計(jì)語言描述算法#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對語言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第42頁!1.6算法與算法分析用偽代碼描述算法偽代碼（Pseudocode）：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。本書采用類C++語言描述算法1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解

intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第43頁!1.6算法與算法分析不使用友元，邏輯上相關(guān)的類認(rèn)為都是友元，可直接訪問任一對象的數(shù)據(jù)函數(shù)參數(shù)表：對類型十分明確的參數(shù)，在參數(shù)表中可不做類型說明為了與C++兼容，本書算法中的數(shù)組下標(biāo)均從0開始數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第44頁!1.7總結(jié)ADT的三個(gè)不同的視圖ADT

邏輯結(jié)構(gòu)操作集合1n數(shù)據(jù)結(jié)構(gòu)

存儲結(jié)構(gòu)算法設(shè)計(jì)1n類

成員變量成員函數(shù)定義視圖設(shè)計(jì)視圖實(shí)現(xiàn)視圖數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第45頁!1.7總結(jié)好的程序設(shè)計(jì)選擇好的數(shù)據(jù)邏輯結(jié)構(gòu)設(shè)計(jì)選擇好的數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計(jì)選擇好的算法支持好的解決問題的方案開發(fā)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第46頁!書面作業(yè)P191-1題，1-2題，1-5題補(bǔ)充題按增長率從小到大的順序排列下列各函數(shù)：數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第47頁!課程介紹教材及參考書《數(shù)據(jù)結(jié)構(gòu)與算法》趙玉蘭等著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)—用面向?qū)ο蠓椒ㄅcC++描述》殷人昆著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏、吳偉民著，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)與算法分析》張銘、劉曉丹譯，電子工業(yè)出版社《ComputerAlgorithms–IntroductiontoDesignandAnalysis》Sarabase，高等教育出版社影印《DataStructuresandAlgorithms》AlfredV.Aho網(wǎng)上閱讀材料數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第48頁!課程介紹學(xué)習(xí)目標(biāo)知識方面掌握基本的數(shù)據(jù)結(jié)構(gòu)掌握數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法以及經(jīng)典算法掌握初步的算法分析技術(shù)能力方面培養(yǎng)算法設(shè)計(jì)能力、程序設(shè)計(jì)能力培養(yǎng)計(jì)算機(jī)思維能力數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第49頁!課程介紹學(xué)習(xí)要求重視課后習(xí)題重視上機(jī)實(shí)驗(yàn)最有害的行為抄襲他人作業(yè)拷貝他人程序數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第50頁!1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計(jì)，并隨著程序設(shè)計(jì)的發(fā)展而發(fā)展程序設(shè)計(jì)的實(shí)質(zhì)是數(shù)據(jù)表示和數(shù)據(jù)處理數(shù)據(jù)表示：如何將數(shù)據(jù)從機(jī)外表示轉(zhuǎn)化為機(jī)內(nèi)表示，存儲在計(jì)算機(jī)（內(nèi)存）中數(shù)據(jù)處理：如何處理機(jī)內(nèi)表示的數(shù)據(jù)，實(shí)現(xiàn)問題求解或完成處理要求《數(shù)據(jù)結(jié)構(gòu)與算法》課程主要討論數(shù)據(jù)表示和數(shù)據(jù)處理過程中的基本問題。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第51頁!1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展結(jié)構(gòu)化階段應(yīng)用領(lǐng)域：科學(xué)計(jì)算與非數(shù)值性數(shù)據(jù)處理處理的數(shù)據(jù)：數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)70’s80’s90’s70’s—80’s非數(shù)值問題猛增

數(shù)據(jù)之間的關(guān)系：產(chǎn)生了數(shù)據(jù)結(jié)構(gòu)，提出了程序結(jié)構(gòu)模塊化，開始注意數(shù)據(jù)表示和操作的結(jié)構(gòu)化數(shù)據(jù)結(jié)構(gòu)＋算法＝程序1968年，D.E.Knuth所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》卷《基本算法》，首次較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及定義在數(shù)據(jù)上的操作，開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的課程體系。同年，《數(shù)據(jù)結(jié)構(gòu)》作為一門獨(dú)立的課程在計(jì)算機(jī)科學(xué)的學(xué)科課程中開始出現(xiàn)。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第52頁!1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——D.E.Knuth1938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming他計(jì)劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎(jiǎng)。此時(shí)，他年僅36歲。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第53頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)值問題建立的模型是數(shù)學(xué)方程問題求解的核心是數(shù)值計(jì)算例彈道計(jì)算<v0,α,…>矩陣運(yùn)算M1×M2×M3×…×Mn方程組求解定積分?jǐn)?shù)學(xué)方程數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第54頁!1.2數(shù)據(jù)結(jié)構(gòu)電話號碼簿的結(jié)構(gòu)：按照單位排列電話號碼內(nèi)蒙古黨委內(nèi)蒙古政府黨政機(jī)關(guān)理工學(xué)院計(jì)算機(jī)系網(wǎng)絡(luò)中心計(jì)算中心計(jì)算機(jī)學(xué)院內(nèi)蒙古大學(xué)內(nèi)蒙古工業(yè)大學(xué)大專院校醫(yī)療衛(wèi)生交通運(yùn)輸呼和浩特市電話號碼簿數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第55頁!1.2數(shù)據(jù)結(jié)構(gòu)例2學(xué)籍管理問題——表結(jié)構(gòu)姓名學(xué)號性別年齡民族系專業(yè)入學(xué)時(shí)間王小林060631男18漢族計(jì)算機(jī)計(jì)算機(jī)科學(xué)2006.9陳紅060632女20蒙族計(jì)算機(jī)計(jì)算機(jī)應(yīng)用2006.9劉建平060633男19回族計(jì)算機(jī)電子商務(wù)2006.9……..……..…….…….……………….數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第56頁!1.2數(shù)據(jù)結(jié)構(gòu)例4教學(xué)計(jì)劃編排問題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫原理C7C2,

C4計(jì)算機(jī)原理C6C3,C4數(shù)據(jù)結(jié)構(gòu)C5C1,C2程序設(shè)計(jì)C4C1離散數(shù)學(xué)C3無計(jì)算機(jī)導(dǎo)論C2無高等數(shù)學(xué)C1先修課課程名稱編號C1C2C3C4C6C5C7數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第57頁!1.2數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)（Data）：是信息的載體，在計(jì)算機(jī)科學(xué)中指所有能輸入到計(jì)算機(jī)中，并能被計(jì)算機(jī)程序識別和處理的符號集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第58頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對象（DataObject）：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)元素的集合。整數(shù)數(shù)據(jù)對象，包括{0,1,2,…}字母數(shù)據(jù)對象，包括{‘A’,’B’,…,’Z’,’a’,’b’,…,’z’}學(xué)生數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第59頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型（DataType）：指定一種數(shù)據(jù)對象的類型。定義為一個(gè)值的集合以及定義在該值集合上的一組操作的總稱。C++語言的數(shù)據(jù)類型基本類型結(jié)構(gòu)類型整型實(shí)型字符型枚舉型指針型數(shù)組型結(jié)構(gòu)型共用體類數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第60頁!1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究的對象包括三個(gè)方面數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系，即指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或鄰接關(guān)系數(shù)據(jù)的存儲結(jié)構(gòu)指數(shù)據(jù)元素在計(jì)算機(jī)中的存儲結(jié)構(gòu)，如某個(gè)電話號碼在號碼本上的位置運(yùn)算的集合定義在該結(jié)構(gòu)上的一組操作，如輸入/讀取、檢索/查找、插入、刪除、更新等數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第61頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)（直接）前驅(qū)（Previous）與（直接）后繼（Next）如果有<a,b>，稱a是b的（直接）前驅(qū)，b是a的（直接）后繼笛卡兒積（DescartesSet）給定兩個(gè)集合A和B，如果有序偶對的個(gè)分量是A的一個(gè)元素，第二個(gè)分量是B的一個(gè)元素，則所有這種有序偶對的集合稱為集合A和B的笛卡兒積記為：A×B＝{<x,y>|xA∧yB}數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第62頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)說明從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)可以看作是從具體問題抽象出來的數(shù)據(jù)模型面向問題，面向用戶分類（根據(jù)數(shù)據(jù)元素間的不同特性）非線性結(jié)構(gòu)線性結(jié)構(gòu)集合樹形結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第63頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)集合例5DS=(D,R2)

D={d1,d2,d3,d4,d5,d6}R2={d1D,d2D,d3D,d4D,d5D,d6D}結(jié)構(gòu)中的數(shù)據(jù)元素只具有“同屬于一個(gè)集合”的關(guān)系d2d6d1d3d5d4數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第64頁!1.3數(shù)據(jù)的邏輯結(jié)構(gòu)圖形或網(wǎng)狀結(jié)構(gòu)例7DS=(D,R4)D={d1,d2,d3,d4,d5}R4={<d1,d2>,<d3,d1>,<d1,d4>,<d5,d1>,<d2,d3>,<d5,d4>,<d3,d5>}結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系d1d2d3d4d5數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第65頁!1.4抽象數(shù)據(jù)類型數(shù)據(jù)類型一個(gè)值的集合以及定義在該值集合上的一組操作的總稱規(guī)定了該數(shù)據(jù)類型的取值范圍和對這些數(shù)據(jù)所能采取的操作例，C++中的整型變量抽象抽出問題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)，是對具體事物的一個(gè)概括隱藏了繁雜的細(xì)節(jié)，只保留實(shí)現(xiàn)目標(biāo)所必需的信息例，地圖、駕駛汽車數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第66頁!1.4抽象數(shù)據(jù)類型ADT的描述ADTADT-name{

Data數(shù)學(xué)模型或數(shù)據(jù)的邏輯結(jié)構(gòu)

Operations //操作集

Constrictor //構(gòu)造操作，初始化 Initialvalues：用于初始化的值。Process：初始化。

Operation1 Input：輸入數(shù)據(jù)（參數(shù)）。Preconditions：執(zhí)行本操作前系統(tǒng)必須處于的狀態(tài)。Process：操作。Output：輸出。Postconditions：執(zhí)行本操作后系統(tǒng)所處狀態(tài)。

Operation2 …… Operationk}//ADT-name數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第67頁!1.4抽象數(shù)據(jù)類型

Add(x,y):NaturalNumber

if(x+y<=MaxInt)返回x+yelse返回MaxInt

Subtract(x,y):NaturalNumber

if(x<y)返回0else返回x-y

Equal(x,y):Boolean

if(x==y)返回Trueelse返回False

Successor(x):NaturalNumber

if(x==MaxInt)返回xelse返回x+1

……}//

NaturalNumber

數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第68頁!1.5數(shù)據(jù)的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)例9LS={D,R}D={a,b,c,d,e}R={<a,b>,<b,c>,<c,d>,<d,e>}abcde10241026102810301032存儲空間連續(xù)保持了邏輯關(guān)系數(shù)據(jù)元素的存儲位置abcd

e數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第69頁!1.5數(shù)據(jù)的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的基本思想用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素?cái)?shù)據(jù)元素之間的邏輯關(guān)系是由元素的存儲位置來（隱式）表示的鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本思想用一組任意的存儲單元存儲數(shù)據(jù)元素?cái)?shù)據(jù)元素之間的邏輯關(guān)系是用指針來（顯式）表示的數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第70頁!1.6算法與算法分析算法（Algorithms）定義對具體問題的求解步驟，是指令的有限序列。特性有窮性一個(gè)算法必須在執(zhí)行有限步驟后終止，且每一步都在有限時(shí)間完成。確定性算法中的每條指令必須有確切的含義，無二義性。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第71頁!1.6算法與算法分析算法≠程序程序是對一個(gè)算法使用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)，是對算法的精確描述，可在計(jì)算機(jī)上執(zhí)行算法一定要滿足有窮性而程序并不一定滿足程序設(shè)計(jì)的核心是算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第72頁!1.6算法與算法分析算法的正確性對任一合法的輸入，算法結(jié)束后得到正確結(jié)果。體現(xiàn)在兩個(gè)方面求解問題的方法（算法）是正確的；對算法實(shí)現(xiàn)（程序）是正確的。算法的正確性由問題領(lǐng)域的理論和定理保證和證明。如高斯迭代法，其正確性是由線性代數(shù)的理論證明。程序的正確性通過軟件測試來判定，但測試無法保證程序是絕對正確的。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第73頁!1.6算法與算法分析最優(yōu)性（Optimality）問題的下界（LowerBounds）問題固有的復(fù)雜度，解決該問題至少要做的工作量算法的上界（UpperBounds）算法工作量的上界最優(yōu)算法算法的上界＝問題的下界2m問題的下界算法的上界數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第74頁!1.6算法與算法分析例10在三個(gè)整數(shù)中求最大者max(inta,intb,intc){

if(a>b){

if(a>c)returna;

elsereturnc;

}

else{

if(b>c)returnb;

elsereturnc;

}}/*無需額外存儲空間，只需兩次比較*/max(inta[3]){intc,inti;c=a[0];for(i=1;i<3;i++)if(a[i]>c)c=a[i];returnc;}/*需要兩個(gè)額外的存儲空間，兩次比較，至少一次賦值*/數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第75頁!1.6算法與算法分析度量算法效率的方法之二——算法分析算法分析：對一個(gè)算法執(zhí)行時(shí)所消耗的兩種計(jì)算機(jī)資源（時(shí)間和空間）進(jìn)行事前估算。如何度量時(shí)間復(fù)雜度空間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第76頁!1.6算法與算法分析步簡化假設(shè)每條簡單語句執(zhí)行一次的時(shí)間都是單位時(shí)間1算法的執(zhí)行時(shí)間＝∑每條語句執(zhí)行次數(shù)

——精確計(jì)算出每條語句執(zhí)行次數(shù)之和很困難第二步簡化用算法中基本語句的執(zhí)行次數(shù)來度量基本語句（基本操作）：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成正比的語句算法的執(zhí)行時(shí)間＝基本語句的執(zhí)行次數(shù)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第77頁!1.6算法與算法分析由以上分析，算法的執(zhí)行時(shí)間T是輸入尺寸n的函數(shù)，記作T(n)＝f(n)。為了客觀反映一個(gè)算法的執(zhí)行時(shí)間，可以用算法中基本語句的執(zhí)行次數(shù)的數(shù)量級來度量算法的工作量，稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度，通常用大O記號表示。數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第78頁!1.6算法與算法分析時(shí)間復(fù)雜度分析舉例x++;for(inti=1;i<=n;i++)x++;for(inti=1;i<=n;i++)for(intj=1;j<=i-1;j++)x++;基本語句：x++執(zhí)行次數(shù)：1時(shí)間復(fù)雜度T(n)=1=O(1)基本語句：x++執(zhí)行次數(shù)：n時(shí)間復(fù)雜度T(n)=n=O(n)基本語句：x++執(zhí)行次數(shù)：時(shí)間復(fù)雜度T(n)==O(n2)數(shù)據(jù)結(jié)構(gòu)與算法張清華大學(xué)出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第79頁!1.6算法與算法分析例12①sum=0;②for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++;③for(k=1;k<=n;k++)a[k]=k-1;①的基本語句：sum=0執(zhí)行次數(shù)：1時(shí)間復(fù)雜度：O(1)②的基本語句：sum++執(zhí)行次數(shù)：n2