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

1、1,數(shù)據(jù)結(jié)構(gòu),2,課程相關(guān)信息,教材：數(shù)據(jù)結(jié)構(gòu)，劉大有等編著，高等教育出版社，2010年9月. 參考書(shū)目：清華大學(xué)出版社、高等教育出版社和機(jī)械出版社等出版的數(shù)據(jù)結(jié)構(gòu)教材. 教學(xué)形式：理論實(shí)驗(yàn) 考核方式：考試,3,參考書(shū) 1、數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏、吳偉民編著 清華大學(xué)出版社。 2、數(shù)據(jù)結(jié)構(gòu) （用面向?qū)ο蠓椒ㄅcC+描述） 殷人昆、陶永雷等編著 清華大學(xué)出版社,4,教學(xué)計(jì)劃,第一章 緒論(算法分析基礎(chǔ)) 第二章 線性表、堆棧、隊(duì)列 第三章 數(shù)組、字符串 第四章 樹(shù) 第五章 圖 第六章 遞歸 第七章 排序 第八章 查找,5,第一章 緒論,1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)概念 1.3 算法 1

2、.4 算法的正確性證明 1.5 算法分析基礎(chǔ),6,1.1 為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)學(xué)科中一門(mén)重要的專業(yè)基礎(chǔ)課。 提高計(jì)算機(jī)的工作效率。 是程序設(shè)計(jì)的重要基礎(chǔ)； 是許多計(jì)算機(jī)專業(yè)課的基礎(chǔ)，如算法分析、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)等。,7,最短路徑算法在物流配送問(wèn)題中的應(yīng)用； 樹(shù)結(jié)構(gòu)在數(shù)據(jù)挖掘領(lǐng)域中的應(yīng)用； 散列技術(shù)在數(shù)據(jù)加密領(lǐng)域中的應(yīng)用； 查找技術(shù)在數(shù)據(jù)庫(kù)領(lǐng)域中的應(yīng)用； 倒排文件、查找算法在搜索引擎中的應(yīng)用。,8,第一章 緒論,1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎(chǔ),9,例 個(gè)人書(shū)庫(kù)管理程序所要處理的數(shù)據(jù)可能是如下的表

3、格。,10,1.2 數(shù)據(jù)結(jié)構(gòu)概念1. 數(shù)據(jù),數(shù)據(jù)是對(duì)象的表示。 計(jì)算機(jī)程序要處理的“原料”，它可以被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。 包括：數(shù)值、文字、表格、圖像、聲音、源程序等。,11,數(shù)據(jù)元素,是組成數(shù)據(jù)的基本單位。 在程序中通常把一個(gè)數(shù)據(jù)元素作為一個(gè)整體來(lái)考慮和處理。 數(shù)據(jù)元素還可被稱為結(jié)點(diǎn)或頂點(diǎn)。 例如，在上表中，把其中的每一行（代表一本書(shū)）作為一個(gè)基本單位來(lái)考慮。,12,數(shù)據(jù)項(xiàng),一個(gè)數(shù)據(jù)元素含有若干個(gè)數(shù)據(jù)項(xiàng)。 例如，在上表數(shù)據(jù)中，每個(gè)數(shù)據(jù)元素由登錄號(hào)、書(shū)號(hào)、書(shū)名、作者、出版社和價(jià)格六個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。 數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)的最小單位。,13,例 電話號(hào)碼薄的查詢問(wèn)題。 (a1，b1 ), (a2

4、，b2), (an，bn ),14,例2 學(xué)生自然情 況查詢問(wèn)題。,15,2. 邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素及其間的邏輯關(guān)系。 在個(gè)人書(shū)庫(kù)管理程序中，各數(shù)據(jù)元素之間在邏輯上有一種線性關(guān)系，它指出了10個(gè)數(shù)據(jù)元素在表中的排列順序。,16,有些書(shū)也將數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹(shù)和圖等四種類型。其中，集合的特點(diǎn)是：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，別無(wú)其他關(guān)系。,集合,線性結(jié)構(gòu),樹(shù),圖,17,邏輯結(jié)構(gòu)的形式化表示,邏輯結(jié)構(gòu)表示為二元組L=(N, R)， N是結(jié)點(diǎn)的有限集合 R是N上的關(guān)系集合,18,例 L=(N,R)， N=a, b, c, d, e , R=r， r=

5、, , , ,若a，bN，且關(guān)系r，則稱a是b的前趨結(jié)點(diǎn)，稱b是a的后繼結(jié)點(diǎn)，稱a和b是相鄰結(jié)點(diǎn)； 如果不存在aN，使r ，則稱b為始結(jié)點(diǎn)； 如果不存在bN ，使r，則稱a為終結(jié)點(diǎn)； 既非始結(jié)點(diǎn)又非終結(jié)點(diǎn)的結(jié)點(diǎn)被稱為內(nèi)結(jié)點(diǎn)。,19,例 L=(N,R)， N=k1,k2,k9, R=r，r=, , , , , , , ,20,邏輯結(jié)構(gòu)的分類 線性結(jié)構(gòu) 結(jié)構(gòu)中有且僅有一個(gè)始結(jié)點(diǎn)和一個(gè)終結(jié)點(diǎn)，始結(jié)點(diǎn)只有一個(gè)后繼結(jié)點(diǎn)，終結(jié)點(diǎn)只有一個(gè)前趨結(jié)點(diǎn)，每個(gè)內(nèi)結(jié)點(diǎn)有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。 非線性結(jié)構(gòu)（樹(shù)、圖） 結(jié)構(gòu)中的結(jié)點(diǎn)可能有多個(gè)前趨結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn)。,21,3存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏

6、輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪問(wèn)方式等的總稱。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種由邏輯結(jié)構(gòu)到存儲(chǔ)空間的映射。 個(gè)人書(shū)庫(kù)數(shù)據(jù)，在計(jì)算機(jī)中可以有多種存儲(chǔ)表示。如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤(pán)上，等等。,22,存儲(chǔ)結(jié)構(gòu)分類,1）順序存儲(chǔ)結(jié)構(gòu) 把一組結(jié)點(diǎn)存放在地址相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系用存儲(chǔ)單元的自然順序關(guān)系表達(dá)。,23,23,2）鏈接存儲(chǔ)結(jié)構(gòu) 在結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)中附加指針字段，兩個(gè)結(jié)點(diǎn)的邏輯后繼關(guān)系用指針的指向來(lái)表達(dá)。,(a)可用存儲(chǔ)空間,24,存儲(chǔ)結(jié)構(gòu)分類,3）索引存儲(chǔ)結(jié)構(gòu) 索引表把整數(shù)索引值映射到結(jié)點(diǎn)的存儲(chǔ)地址。 索引表存儲(chǔ)一串指

7、針，每個(gè)指針指向存儲(chǔ)區(qū)域的一個(gè)數(shù)據(jù)結(jié)點(diǎn)。,25,存儲(chǔ)結(jié)構(gòu)分類,4）散列存儲(chǔ)結(jié)構(gòu) 適用于大數(shù)據(jù)量、高速檢索的場(chǎng)合。 索引存儲(chǔ)的一種延伸和擴(kuò)展，利用散列函數(shù)進(jìn)行索引值的計(jì)算，并通過(guò)索引表求出結(jié)點(diǎn)的指針地址。,26,存儲(chǔ)結(jié)構(gòu)總結(jié),順序、鏈接、索引和散列存儲(chǔ)結(jié)構(gòu)，可以單獨(dú)使用，也可以組合使用。 存儲(chǔ)結(jié)構(gòu)要正確反映邏輯結(jié)構(gòu)，并便于操作。,27,4. 對(duì)數(shù)據(jù)的操作,插入 刪除 修改 排序 查找,28,數(shù)據(jù)結(jié)構(gòu)的定義： 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及他們之間的關(guān)系，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法。,5.數(shù)據(jù)結(jié)構(gòu)的概念,29,數(shù)據(jù)結(jié)構(gòu)的概念,按某種邏輯關(guān)系將一批數(shù)據(jù)元素組織起來(lái)；

8、 按一定的存儲(chǔ)方式把它們存儲(chǔ)起來(lái)； 在數(shù)據(jù)上定義需要施加的操作。,30,數(shù)據(jù)結(jié)構(gòu)課程的目的,從對(duì)問(wèn)題抽象和求解的角度來(lái)學(xué)習(xí)常用的數(shù)據(jù)結(jié)構(gòu)，闡明其內(nèi)在的邏輯關(guān)系和在計(jì)算機(jī)中的存儲(chǔ)表示，以及刻畫(huà)施加于其上之各種操作的算法。 學(xué)習(xí)上述理論知識(shí)，綜合運(yùn)用相關(guān)知識(shí)，再結(jié)合上機(jī)實(shí)踐，使我們具備求解比較復(fù)雜的問(wèn)題的能力，即掌握問(wèn)題求解建模，選擇恰當(dāng)數(shù)據(jù)結(jié)構(gòu)，或構(gòu)造新的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)較優(yōu)算法，證明算法（或算法之關(guān)鍵步驟）正確性，分析算法的時(shí)空復(fù)雜性，對(duì)算法編程、調(diào)試等能力。,31,數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的集合的總稱。 抽象數(shù)據(jù)類型：由一組數(shù)據(jù)結(jié)構(gòu)和在該組數(shù)據(jù)結(jié)構(gòu)上的一組操作所組成

9、。,32,第一章 緒論,1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)的概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎(chǔ),33,計(jì)算機(jī)解決問(wèn)題的步驟： 從具體問(wèn)題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型； 設(shè)計(jì)解此模型的方法； 編出程序、進(jìn)行測(cè)試、調(diào)試，直至得到最終解答。 計(jì)算機(jī)處理問(wèn)題，以適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，制定出的切實(shí)可行的方法和步驟計(jì)算機(jī)算法。,1.3 算法1.算法的概念,34,計(jì)算機(jī)算法與數(shù)據(jù)結(jié)構(gòu)密切相關(guān):算法無(wú)不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。 對(duì)數(shù)據(jù)的操作是由計(jì)算機(jī)來(lái)完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改等算法 。 1976年，沃斯提出：算法+數(shù)據(jù)結(jié)

10、構(gòu)=程序,算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系,35,算法由有限條指令構(gòu)成，規(guī)定了解決特定問(wèn)題的一系列操作。 算法具有5個(gè)特性： (1)有限性：一個(gè)算法在執(zhí)行有限步后必然終止。 (2)確定性：算法中的每條指令都必須是清楚的，指令無(wú)二義性，相同的輸入必須有相同的輸出。 (3)輸入：具有0個(gè)或0個(gè)以上由外界提供的量。 (4)輸出：產(chǎn)生1個(gè)或多個(gè)結(jié)果。 (5)可行性：每條指令都十分基本，原則上可由人僅用筆和紙?jiān)谟邢薜臅r(shí)間內(nèi)也能完成。 算法與程序的區(qū)別 表現(xiàn)形式不同。 是否具備有窮性。,36,算法可以用自然語(yǔ)言、數(shù)學(xué)語(yǔ)言、程序設(shè)計(jì)語(yǔ)言或約定的任何符號(hào)語(yǔ)言來(lái)描述。如類Pascal語(yǔ)言、C語(yǔ)言或偽代碼等。 ADL語(yǔ)言直觀

11、方便。,2.算法描述語(yǔ)言ADL,37,算法描述語(yǔ)言ADL的格式 算法(變量i1,變量im.變量j1,變量jn)/單行注釋（或/*/多行注釋） . 本步驟的概括說(shuō)明 . 本步驟的概括說(shuō)明 語(yǔ)句序列. ,38, 表達(dá)式 算術(shù)運(yùn)算符 +,-,*,/,DIV,MOD, , 關(guān)系運(yùn)算符= 、 、 邏輯運(yùn)算符AND，OR，NOT 邏輯常量 true，false 集合運(yùn)算符 ，（差）， 語(yǔ)句 每條語(yǔ)句都用“.”作為結(jié)束符 賦值語(yǔ)句 a b. a b. a b c.,39, 條件語(yǔ)句 1) IF THEN (語(yǔ)句1. . 語(yǔ)句m ). 2) IF THEN (語(yǔ)句1. . 語(yǔ)句m ). ELSE (語(yǔ)句1.

12、. 語(yǔ)句n ). 3) CASE DO ( : (語(yǔ)句1. .語(yǔ)句n1). : 語(yǔ)句1. .語(yǔ)句nm).,40,循環(huán)語(yǔ)句 1) WHILE DO (語(yǔ)句1. . 語(yǔ)句n ). 2) FOR = TO STEP DO (語(yǔ)句1. . 語(yǔ)句n ). 3) FOR DO (語(yǔ)句1. . 語(yǔ)句n ).,41,轉(zhuǎn)移語(yǔ)句 GOTO () . EXIT 語(yǔ)句 結(jié)束本層WHILE或者FOR循環(huán)的執(zhí)行 RETURN 語(yǔ)句 指出算法執(zhí)行的終點(diǎn) 其它 輸入語(yǔ)句：READ(x) /讀取輸入值賦給變量x 輸出語(yǔ)句：PRINT(),42,例 A是一個(gè)含有n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求A之最大和最小元素的算法。 算法SM(

13、A, n . max,min) SM1. 初始化 maxminA1. SM2. 比較 FOR I=2 TO n DO /求最大和最小元素 ( IF AI max THEN maxAI. IF AI min THEN minAI) . ,43,ADL 的特點(diǎn),書(shū)寫(xiě)簡(jiǎn)便 不必考慮過(guò)多程序設(shè)計(jì)語(yǔ)言的細(xì)節(jié) 例：交換a和b的值 易于理解 不同編程習(xí)慣的人交流算法 不必考慮與算法無(wú)關(guān)的內(nèi)容（開(kāi)發(fā)及運(yùn)行環(huán)境、編譯狀態(tài)）,44,3. 算法的評(píng)價(jià)準(zhǔn)則 評(píng)估算法性能的5條準(zhǔn)則 正確性 時(shí)間復(fù)雜性 占用空間 可讀性 魯棒性,45,1)正確性 說(shuō)一個(gè)算法是正確的，如果對(duì)于一切合法的輸入數(shù)據(jù)，該算法執(zhí)行有限時(shí)間都能產(chǎn)生

14、正確的結(jié)果。 具體包括兩方面：一是解決問(wèn)題的方法；二是實(shí)現(xiàn)這一方法的一系列指令(步驟、語(yǔ)句)。 證明相關(guān)的引理和定理，以確認(rèn)一個(gè)算法所用方法的正確性； 證明一系列語(yǔ)句確實(shí)做了符合規(guī)定的操作.,46,語(yǔ)句正確性，大體可分為四個(gè)層次： 算法不含語(yǔ)法錯(cuò)誤； 算法對(duì)于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 算法對(duì)于精心選擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)，能夠得出滿足要求的結(jié)果； 算法對(duì)一切合法的輸入數(shù)據(jù)，都能產(chǎn)生滿足要求的結(jié)果。,47,2) 時(shí)間復(fù)雜性 算法的實(shí)際執(zhí)行時(shí)間是不是時(shí)間復(fù)雜性的理想度量呢? 不是。 其原因是： 算法的實(shí)際執(zhí)行時(shí)間依賴于機(jī)器。同一個(gè)算法在不同機(jī)器上的執(zhí)行時(shí)間不一定相同。 算

15、法的實(shí)際執(zhí)行時(shí)間還依賴于編寫(xiě)算法的程序設(shè)計(jì)語(yǔ)言。一個(gè)用 C 或 Pascal 編寫(xiě)的算法可能要比用 BASIC 語(yǔ)言編寫(xiě)的算法快 20 倍。,48,3) 占用的存儲(chǔ)空間 包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間。 算法在運(yùn)行過(guò)程中所占用的存儲(chǔ)空間的大小被定義為算法的空間復(fù)雜性。它包括局部變量所占用的存儲(chǔ)空間和系統(tǒng)為了實(shí)現(xiàn)遞歸所使用的堆棧這兩個(gè)部分。算法的空間復(fù)雜性一般以數(shù)量級(jí)的形式給出。,49,4) 可讀性 最簡(jiǎn)單、最直接的算法盡管不一定是最有效的，但卻具有良好的可讀性?？勺x性好的算法其正確性證明比較容易（即其正確性易于保證），同

16、時(shí)便于設(shè)計(jì)、修改、閱讀和調(diào)試，可見(jiàn)可讀性是十分重要的。 對(duì)于那些需經(jīng)常使用的算法來(lái)說(shuō)，高效率比可讀性更為重要。,50,5) 魯棒性 對(duì)有缺失、有噪聲或有錯(cuò)誤的輸入數(shù)據(jù)，算法應(yīng)具有較強(qiáng)的應(yīng)付能力。如，能對(duì)輸入數(shù)據(jù)語(yǔ)法語(yǔ)義檢驗(yàn)、提出修改錯(cuò)誤的建議并提供重新輸入的機(jī)會(huì)。,51,1.4 算法的正確性證明,對(duì)于一個(gè)算法來(lái)說(shuō)正確性是前提，也是最重要的。 對(duì)明顯是正確的算法，可通過(guò)上機(jī)調(diào)試驗(yàn)證其正確性。調(diào)試用的數(shù)據(jù)要精心挑選，以保證算法對(duì)“所有的”數(shù)據(jù)都是正確的; 只要調(diào)試找出一組數(shù)據(jù)使算法失敗(即計(jì)算結(jié)果不正確)，就能否定整個(gè)算法的正確性; 算法的正確性一般通過(guò)數(shù)學(xué)方法進(jìn)行推理證明，常用的數(shù)學(xué)方法除了直接

17、證明法外，還有反證法和數(shù)學(xué)歸納法。,52,第一章 緒論,1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)的概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎(chǔ),53,Testing (測(cè)試),Black Box Methods 黑盒法 側(cè)重測(cè)試程序的功能，不考慮程序是如何實(shí)現(xiàn)的，即代碼結(jié)構(gòu)。 設(shè)計(jì)測(cè)試用例，檢查能否得到預(yù)想的結(jié)果。 White Box Methods 白盒法 側(cè)重測(cè)試程序的代碼結(jié)構(gòu) Statement Coverage 語(yǔ)句覆蓋: 使程序中的每一條語(yǔ)句都至少執(zhí)行一次。 Decision Coverage 分支覆蓋 ：使程序中的每一個(gè)分枝都至少執(zhí)行一次。,54,1.

18、反證法,1)要證明定理 T 是正確的，首先假定 T是錯(cuò)誤的 2)使用正確的命題和正確的推理規(guī)則進(jìn)行推理, 若出現(xiàn)下列條件之一，就會(huì)得出矛盾的結(jié)果： 與已知條件矛盾 與公理矛盾 與證明過(guò)的定理矛盾 自相矛盾 3)由此推出定理 T 是正確的。,55,例 證明沒(méi)有最大的整數(shù),證明：用反證法。 (1) 反面假設(shè)：假設(shè)存在一個(gè)最大整數(shù)，記為N . (2) 由假設(shè)推出矛盾：設(shè)P N 1，因?yàn)镻 是兩個(gè)整數(shù)的和，所以P也是整數(shù)，且 P N . 與 N 是最大整數(shù)矛盾。 (3) 肯定原來(lái)的結(jié)論：因此，沒(méi)有最大的整數(shù)。證畢。,56,2. 數(shù)學(xué)歸納法,數(shù)學(xué)上證明與自然數(shù) N 有關(guān)的命題的一種特殊方法，它主要用來(lái)研

19、究與正整數(shù)有關(guān)的數(shù)學(xué)問(wèn)題。 數(shù)學(xué)歸納法依靠假設(shè)的事實(shí)來(lái)證明定理，是用“有限”步驟解決“無(wú)限”問(wèn)題的一種嚴(yán)格證明方法。,57,數(shù)學(xué)歸納法： 設(shè)T是一個(gè)定理， n是T中的正參數(shù). 數(shù)學(xué)歸納法表明，如果下面兩個(gè)條件為真，則對(duì)于參數(shù)n的任何值，T都是正確的： (1) 基礎(chǔ)歸納：n c 時(shí)，T成立。 (2) 歸納步驟：如果n = k 1 時(shí)T 成立，則n = k 時(shí)T也成立。 其中，c是一個(gè)較小的常量，n c . 通常，證明初始?xì)w納很容易，而證明歸納步驟很難。,58,強(qiáng)歸納法 設(shè)T是一個(gè)定理， n是T中的正參數(shù). 數(shù)學(xué)歸納法表明，如果下面兩個(gè)條件為真，則對(duì)于參數(shù)n的任何值，T都是正確的： (1) 基礎(chǔ)歸

20、納：n c 時(shí)，T成立。 (2) 歸納步驟：如果n = k 1 時(shí)T 成立，則n = k 時(shí)T也成立 (2) 歸納步驟：如果對(duì)于所有的k ( c k n ) T 都成立，則T 對(duì)于 n 也成立。,59,例: 證明由遞歸關(guān)系式T ( n ) T ( n 1 ) 1，T(1) 0，可推出T(n)n 1，其中，n 1 . 證明： 基礎(chǔ)歸納：n 1 時(shí)，T ( 1 ) 1 1 0，結(jié)論成立。 歸納步驟： 假設(shè) T ( n 1 ) n 2 成立（歸納假設(shè)） 往證 T ( n ) n 1 成立。 由遞歸關(guān)系式可知： n 1 時(shí)，有T ( n ) T ( n 1 ) 1 再由歸納假設(shè)： T ( n ) T

21、( n 1 ) 1 n 2 1 n 1 由數(shù)學(xué)歸納法推出T (n) n 1成立，證畢,60,第一章 緒論,1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)的概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎(chǔ),61,1.5 算法分析基礎(chǔ) 在假定算法正確的前提下，用時(shí)間復(fù)雜性作為評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)。 一個(gè)算法的時(shí)間復(fù)雜性是指該算法所執(zhí)行的基本運(yùn)算的次數(shù)。 最優(yōu)算法的定義： 某算法A為最優(yōu)，當(dāng)且僅當(dāng)解決同一領(lǐng)域同一問(wèn)題的所有算法集合SA (ASA)中沒(méi)有一個(gè)算法執(zhí)行的基本運(yùn)算次數(shù)比算法A更少。,62, 決定運(yùn)行時(shí)間的因素： 、問(wèn)題的規(guī)模。 、對(duì)源程序進(jìn)行編譯所需時(shí)間。 、機(jī)器執(zhí)行指令的

22、速度。 、程序中指令重復(fù)執(zhí)行的次數(shù)。 頻度：算法執(zhí)行一次，某一語(yǔ)句實(shí)際被執(zhí)行的 次數(shù)，叫該語(yǔ)句在此算法中的頻度。,63,1.算法時(shí)間復(fù)雜性的分析方法 例 A是一個(gè)含有n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求A之最大和最小元素的算法。 算法SM (A,n . max,min) SM1初始化 maxminA1. SM2比較 FOR i=2 TO n DO ( IF Ai max THEN maxAi. IF Ai min THEN minAi). 算法SM的時(shí)間復(fù)雜性為2(n-1)。,64,例 實(shí)數(shù)數(shù)組R由n個(gè)元素組成，給定一個(gè)實(shí)數(shù)K，試確定K是否是R的元素。 算法F (R, n, K. i) F1 初始化

23、 i 1. F2 比較 WHILE in DO ( IF Ri=K THEN RETURN. i i+1) . 最少比較次數(shù)：1 最大比較次數(shù)：n,65,定義 設(shè)一個(gè)領(lǐng)域問(wèn)題的輸入規(guī)模為n，Dn是該領(lǐng)域問(wèn)題的所有輸入的集合，任一輸入IDn，P(I)是I出現(xiàn)的概率，且滿足 P(I)=1，T(I)是算法在輸入I下所執(zhí)行的基本運(yùn)算次數(shù)。我們定義該算法的期望復(fù)雜性（即該算法的平均復(fù)雜性 ）為： E(n)= P(I)*T(I) 該算法的最壞復(fù)雜性為： W(n)=maxT(I) 該算法的最好復(fù)雜性為： W(n)=minT(I),66,R1 R2 R3 R4 R5 R6 R7 R8 5 20 12 7 30

24、 40 25 16,K=Ri q/n,K!=Ri 1-q,上例中，設(shè)q( 0q1 )為K 在R中的概率,q,67,通過(guò)計(jì)算我們可以得到算法F的期望復(fù)雜性為 E(n)= P(I)*T(I) =(q/n)*1+ (q/n)*2+ (q/n)*n+(1-q)*n n項(xiàng) 1項(xiàng) = q(n+1)/2+(1-q)n 如果已知K在R中，即q=1，則有 E(n)= (n+1) /2 由算法F很容易看出該算法的最壞復(fù)雜性為 W(n)=maxT(i)| 1i n+1=n,68,例 算法 SM 的改進(jìn)算法 BS 算法BS（A , i , j . fmax , fmin） /* 在數(shù)組 A 的第 i 至第 j 個(gè)元素

25、間尋找最大和最小 元素，已知 i j; 假定A 中元素互異 */ BS1. 遞歸出口 IF i j THEN (fmax fmin Ai. RETURN.) IF i j 1 THEN (IF Ai Aj THEN(fmax Aj. fmin Ai). ELSE (fmax Ai. fmin Aj). RETURN). BS2. 取中值 mid (ij)/2 BS3. 遞歸調(diào)用 BS (A, i, mid. Gmax, gmin). BS (A, mid1, j. hmax, hmin). BS4. 合并 fmax maxgmax, hmax. fmin mingmin, hmin. ,69,

26、i=1 mid= 4 j=8 A1 A2 A3 A4 A5 A6 A7 A8 5 20 12 7 30 40 25 16,算法SM的改進(jìn),70,BS(A , i1 , j8 . fmax , fmin) BS1. BS2. mid4 . BS3. BS(A , i1 , j4. gmax , gmin) BS1. BS2. mid2 . BS3. BS(A , i1 , j2. gmax , gmin) BS1. gmax20. gmin5 . RETURN. BS(A , i3 , j4. hmax , hmin) BS1. hmax12. hmin7. RETURN. BS4. gmax2

27、0 . gmin5 . BS(A , i5 , j8. hmax , hmin) BS1. BS2. mid6 . BS3. BS(A , i5 , j6. gmax , gmin) BS1. gmax40. gmin30. RETURN. BS(A , i7 , j8. hmax , hmin) BS1. hmax25. hmin16. RETURN. BS4. hmax40 . hmin16 . BS4. fmax 40 . fmin 5 . ,71,容易看出，BS對(duì)Ai到Aj的不同的輸入都有相同的基本運(yùn)算次數(shù)。設(shè)T(n)表示其基本運(yùn)算次數(shù)，則根據(jù)算法BS的遞歸過(guò)程，有如下的遞歸表達(dá)式：,

28、若 n 是 2 的冪(即存在正整數(shù)k , 使得 n2k )則有 T(n)2T(n/2)22(2T(n/4)2)2 4T(n/4)424(2T(n/8)2)42 8T(n/8)842 2k1T(2)(21222k1)(3n/2)2,72,BS與SM的比較 算法SM和BS的時(shí)間復(fù)雜性均為線性，但因3n/222(n1)，故算法BS優(yōu)于算法SM. 算法BS是遞歸算法，因此它的實(shí)現(xiàn)需要額外的輔助空間棧。,73,例 求下列各程序段時(shí)間復(fù)雜性。 for(i=1;i=n;i+) x+; for(j=1;j=n;j+) for(k=1;k=n;k+) x+; 計(jì)算時(shí)間復(fù)雜度 算法的計(jì)算時(shí)間個(gè)語(yǔ)句頻度 記做 T(

29、n),74,算法運(yùn)行時(shí)間復(fù)雜度：指某算法的基本操作次數(shù)。 基本操作次數(shù)：最里層循環(huán)體內(nèi)簡(jiǎn)單操作的執(zhí)行次數(shù)或遞歸調(diào)用的調(diào)用次數(shù)。 例3 for(i=1;i=n;i+) for(j=1;j=n;j+) x+;,75,確定算法基本運(yùn)算次數(shù)的目的在于能比較功能相同的兩個(gè)算法之間的時(shí)間復(fù)雜性；預(yù)測(cè)隨實(shí)例特性的改變，運(yùn)行時(shí)間的增減情況。 在很多情況下，特別當(dāng)輸入規(guī)模 n 較大時(shí)，確定一個(gè)算法的基本運(yùn)算次數(shù)T，得到T 和 n 之間的函數(shù)關(guān)系非常困難。 算法分析中通常采用大O、大和大來(lái)漸近表示算法的基本運(yùn)算次數(shù)。,2. 復(fù)雜性函數(shù)的漸近表示,76,1892年，保羅巴赫曼(Paul Bachmann)提出了大O

30、表示法，主要用于估計(jì)函數(shù)的增長(zhǎng)速率。 定義 設(shè)f(n)和g(n)是正整數(shù)集到正實(shí)數(shù)集上的函數(shù)，稱f(n)是O(g(n)，當(dāng)且僅當(dāng)存在正的常數(shù)C 和 n0，使得對(duì)任意的n n0 ，有 f(n) Cg(n) . f 和 g 之間關(guān)系的含義是“f(n)的階至多為g(n)”或“f 至多與g 增長(zhǎng)得一樣快” .,大O表示法,77,例 f (n) 3 n 2 是 O(n) . 證明： 由大O的定義，存在C 3，n0 1，使得對(duì)任意的 n n0 ，有3 n 2 3 n 即 f(n) Cg(n) . 例 f (n) 3 log n loglog n 是 O (logn)證明：由大O的定義，存在C 4， n0 2，使得對(duì)任意的 n n0 ，有3 log n loglog n 4 logn 即 f(n) Cg(n) .,78,一個(gè)算法的時(shí)間復(fù)雜性為 O(g(n)，表明它的基本運(yùn)算次數(shù)至多是 g(n) 的某個(gè)常數(shù)倍. O(1) 表示算法的時(shí)間復(fù)雜性為一常數(shù). O(n)、O(n2)、O(n3)、O(nm) 和 O(2n) 分別表示算法時(shí)間復(fù)雜性為線性階的、平方階的、立方階的、多項(xiàng)式階的和指數(shù)階的，其中