導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)

1、關(guān)于導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1第1頁，共74頁，2022年，5月20日，22點36分，星期三2教材計算機算法基礎(chǔ)（第二版）余祥宣等 華中科技大學(xué)出版社參考書：1.計算機算法設(shè)計與分析：王曉東，電子工業(yè)出版社2.算法分析與設(shè)計 ：（美）古德里奇，（美）塔瑪西亞，霍紅衛(wèi)譯 人民郵電出版社 課時安排：28+12考試形式：閉卷成績： 平時50%+考試50%第2頁，共74頁，2022年，5月20日，22點36分，星期三3序計算機算法是計算機科學(xué)和計算機應(yīng)用的核心數(shù)據(jù)結(jié)構(gòu)+算法 = 程序算法（algorithm）是一個在有限時間內(nèi)逐步執(zhí)行某種任務(wù)的過程數(shù)據(jù)結(jié)構(gòu)（data structure）是一種系統(tǒng)組織和訪問

2、數(shù)據(jù)的方法算法：計算機軟件的靈魂第3頁，共74頁，2022年，5月20日，22點36分，星期三4問題求解(Problem Solving)設(shè)計程序證明正確性分析算法理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計策略設(shè)計算法第4頁，共74頁，2022年，5月20日，22點36分，星期三5章節(jié)安排第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu) 第二章 分治法 第三章 貪心方法 第四章 動態(tài)規(guī)劃 第五章 檢索與周游第六章 回溯法第七章 分枝-限界第八章 NP-問題?算法研討環(huán)節(jié) 第5頁，共74頁，2022年，5月20日，22點36分，星期三6第一章 導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)1.1 算法的定義及特性1. 什么是算法？ 算法如數(shù)字、

3、計算一樣，是一個基本概念。 算法是解一類確定問題的任意一種特殊的方法。 在計算機科學(xué)中，算法是使用計算機解一類問題的精確、有效方法的代名詞： 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。第6頁，共74頁，2022年，5月20日，22點36分，星期三72.算法的五個重要特性 確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運算必須要有確切的定義，不能有二義性。 例：不符合確定性的運算 5/0 將6或7與x相加 未賦值變量參與運算第7頁，共74頁，2022年，5月20日，22點36分，星期三82）能行性 算法中有待實現(xiàn)的運算都是基本的運算，原理上每種運算都能由人用紙和筆

4、在有限的時間內(nèi)完成。例：整數(shù)的算術(shù)運算是“能行”的 實數(shù)(無理數(shù))的算術(shù)運算是“不能行”的第8頁，共74頁，2022年，5月20日，22點36分，星期三93）輸入 每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合定義域（或值域）4）輸出 一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關(guān)系的量。第9頁，共74頁，2022年，5月20日，22點36分，星期三105）有窮性 一個算法總是在執(zhí)行了有窮步的運算之后終止。計算過程：只滿足確定性、能行性、輸入、輸出四個特性但不一定能終止的一組規(guī)則。 準(zhǔn)確理解算法和計算過程的區(qū)別： 不能終止的計算過程：操作系統(tǒng)。 算法

5、是“可以終止的計算過程”。 算法的時效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投入到計算機上運行。第10頁，共74頁，2022年，5月20日，22點36分，星期三114. 我們的主要任務(wù) 算法學(xué)習(xí)將涉及5個方面的內(nèi)容： 1）設(shè)計算法：創(chuàng)造性的活動 2）表示算法：思想的表示形式 3）確認算法：證明算法的正確性 程序的證明（程序的形式化證明技術(shù)） 4）分析算法：算法時空特性分析 5）測試程序：“調(diào)試只能指出有錯誤，而不能指出它們 不存在錯誤” 本課程集中于學(xué)習(xí)算法的設(shè)計與分析。通過學(xué)習(xí)，掌握計算機算法設(shè)計和分析基本策略與方法，為設(shè)計更復(fù)雜、更有效的算法奠定基礎(chǔ)。第11頁，共74頁，2022年，5月20日

6、，22點36分，星期三125. 課程關(guān)系 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計語言：結(jié)構(gòu)化設(shè)計 數(shù)學(xué)基礎(chǔ) 非數(shù)值計算領(lǐng)域的基本知識第12頁，共74頁，2022年，5月20日，22點36分，星期三131.2 分析算法1. 分析算法的目的 在于：通過對算法的分析，在把算法變成程序?qū)嶋H運行前，就知道為完成一項任務(wù)所設(shè)計的算法的好壞，從而運行好的算法，改進差的算法，避免無益的人力和物力浪費。 算法分析是計算機領(lǐng)域的古老而前沿的課題。 進行算法分析的基本技術(shù)：抽象第13頁，共74頁，2022年，5月20日，22點36分，星期三142. 重要的假設(shè)和約定1）計算機模型的假設(shè) Turing機模型：計算機形式理論模型 通用計算

7、機模型： 順序計算機 有足夠的“內(nèi)存” 能在固定的時間內(nèi)存取數(shù)據(jù)單元 第14頁，共74頁，2022年，5月20日，22點36分，星期三152）計算的約定 算法的執(zhí)行時間=Fi*ti 其中，F(xiàn)i是算法中用到的某種運算i的次數(shù)， ti是該運算執(zhí)行一次所用的時間。 確定使用什么樣的運算及其執(zhí)行時間。從計算時間上，運算的分類： 時間囿界于常數(shù)的運算： 基本算術(shù)運算，如整數(shù)、浮點數(shù)的加、減、乘、除 字符運算 賦值運算 過程調(diào)用等 特點：盡管每種運算的執(zhí)行時間不同，但一般只花 一個固定量的時間（單位時間）就可完成。第15頁，共74頁，2022年，5月20日，22點36分，星期三162）計算的約定（續(xù)） 其

8、他運算： 字符串操作：與字符串中字符的數(shù)量成正比 記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān) 特點：運算時間無定量 如何分析非時間囿界于常數(shù)的運算：分解成若干時間囿界于常數(shù)的運算。 如：Tstring = Length（String）* tchar第16頁，共74頁，2022年，5月20日，22點36分，星期三173）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞情況下工作的數(shù)據(jù)配置。然后使用這些數(shù)據(jù)配置運行算法，以了解算法的性能。測試數(shù)據(jù)集的生成在目前算法證明與程序正確性證明沒有取得理論上的突破性進展的情況下，是程序測試與算法分析中的關(guān)鍵技術(shù)之一。 作為算法分析的數(shù)據(jù)集：典型特征 作為程序

9、性能測試的數(shù)據(jù)集：對執(zhí)行指標(biāo)產(chǎn)生影響的性質(zhì)第17頁，共74頁，2022年，5月20日，22點36分，星期三183. 如何進行算法分析？ 對算法進行全面分析，可分兩個階段進行：事前分析：就算法本身，通過對其執(zhí)行性能的理論分析， 得出關(guān)于算法特性時間和空間的一個特征 函數(shù)（、）與計算機物理軟硬件沒有 直接關(guān)系。事后測試：將算法編制成程序后實際放到計算機上運行， 收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行 分析判斷直接與物理實現(xiàn)有關(guān)。第18頁，共74頁，2022年，5月20日，22點36分，星期三191）事前分析目的：試圖得出關(guān)于算法執(zhí)行特性的一種形式描 述，以“理論上”衡量算法的“好壞”。如何給出反

10、映算法執(zhí)行特性的描述？ 最直接方法：統(tǒng)計算法中各種運算的執(zhí)行情況，包括： 引用了哪些運算 每種運算被執(zhí)行的次數(shù) 該種運算執(zhí)行一次所花費的時間等。 算法的執(zhí)行時間=Fi*ti第19頁，共74頁，2022年，5月20日，22點36分，星期三20頻率計數(shù) 例： xx+y for i 1 to n do for i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b) (c) 分析： (a)： xx+y執(zhí)行了1次 (b)： xx+y執(zhí)行了n次 (c)： xx+y執(zhí)行了n2次 定義： 頻率計數(shù)：一條語句或一種運算在算法

11、（或程序）體中的執(zhí)行次數(shù)。第20頁，共74頁，2022年，5月20日，22點36分，星期三21一條語句在整個程序運行時實際執(zhí)行時間= 頻率計數(shù) * 每執(zhí)行一次該語句所需的時間 如何刻畫算法執(zhí)行特性的形式描述實際執(zhí)行時間受約于諸多實際因素，如機器類型、編程與語言、操作系統(tǒng)等，沒有統(tǒng)一的描述模型。在事前分析中，只限于確定與所使用的機器及其他環(huán)境因素?zé)o關(guān)的頻率計數(shù)，依此建立理論分析模型。第21頁，共74頁，2022年，5月20日，22點36分，星期三22數(shù)量級 語句的數(shù)量級：語句的執(zhí)行頻率 例：1，n ，n2 算法的數(shù)量級：算法所包含的所有語句的執(zhí) 行頻率之和。算法的數(shù)量級從本質(zhì)上反映了一個算法的執(zhí)

12、行特性。例：假如求解同一個問題的三個算法分別具有n， n2 ， n3數(shù) 量級。 若n=10，則可能的執(zhí)行時間將分別是10，100，1000個 單位時間與環(huán)境因素?zé)o關(guān)。第22頁，共74頁，2022年，5月20日，22點36分，星期三23 計算時間/頻率計數(shù)的表示函數(shù) 通過事前分析給出算法計算時間（頻率計數(shù)）的一個函數(shù)表示形式，一般記為與輸入規(guī)模n有關(guān)的函數(shù)形式：f(n)注：最高次項與函數(shù)整體的關(guān)系空間特性分析（略） 第23頁，共74頁，2022年，5月20日，22點36分，星期三242）事后測試目的：運行程序，確定程序?qū)嶋H耗費的時間與空間，驗證先前的分析結(jié)論包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)

13、計的算法。分析手段：作時、空性能分布圖第24頁，共74頁，2022年，5月20日，22點36分，星期三254. 計算時間的漸近表示記：算法的計算時間為f(n) 數(shù)量級限界函數(shù)為g(n)其中， n是輸入或輸出規(guī)模的某種測度。 f(n)表示算法的“實際”執(zhí)行時間與機器及語言有關(guān)。 g(n)是形式簡單的函數(shù)，如nm，logn，2n，n!等。是事前分析中通過對計算時間或頻率計數(shù)統(tǒng)計分析所得的、與機器及語言無關(guān)的函數(shù)。 以下給出算法執(zhí)行時間：上界（）、下界（）、“平均”（ ）的定義。第25頁，共74頁，2022年，5月20日，22點36分，星期三261）上界函數(shù)定義1 如果存在兩個正常數(shù)c和n0，對于所

14、有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n)含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個上界函數(shù)。 f(n)的數(shù)量級就是g(n)。試圖求出最小的g(n)，使得f(n) = (g(n)。 第26頁，共74頁，2022年，5月20日，22點36分，星期三27F(n)=3n+2 可取c4，n02，O(n)F(n)=100n+6 可取 c=101，n06，O(n)F(n)=2n2+11n-10 可取c=3， n010，O(n2)F(n)=62n+n2 可取c =7，n0=4 ，O

15、(2n)第27頁，共74頁，2022年，5月20日，22點36分，星期三28多項式定理:定理1 若A(n) = amnm+a1n+a0是一個m次多項 式，則有A(n) = (nm) 即：變量n的固定階數(shù)為m的任一多項式，與此多 項式的最高階nm同階。 證明：取n0=1,當(dāng)nn0時，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 則，定理得證。第28頁，共74頁，2022年，5月20日，22點36分，星期三29 計算時間的數(shù)量級對算法有效性的影響 數(shù)量級的

16、大小對算法的有效性有決定性的影響。 例：假設(shè)解決同一個問題的兩個算法，它們都有n個輸入，計算時間的數(shù)量級分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運算。 n=2048：分別需要4194304和22528次運算。 分析：在n加倍的情況下，一個(n2)的算法計算時間增長4倍，而一個(nlogn)算法則只用2倍多一點的時間即可完成。第29頁，共74頁，2022年，5月20日，22點36分，星期三30 算法分類（計算時間）多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。 常見的多項式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (

17、n3)指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時間限界函數(shù)： (2n) (n！) 0。 第49頁，共74頁，2022年，5月20日，22點36分，星期三50第50頁，共74頁，2022年，5月20日，22點36分，星期三51 特殊形態(tài)的二元樹 滿二元樹：深度為k且有2k-1個結(jié)點的二元樹 第51頁，共74頁，2022年，5月20日，22點36分，星期三52 完全二元樹：一棵有n個結(jié)點深度為k的二元樹，當(dāng)它的結(jié)點相當(dāng)于深度為k的滿二元樹中編號為1到n的結(jié)點時，稱該二元樹是完全的。 完全二元樹的葉子結(jié)點至多出現(xiàn)在相鄰的兩級上。 完全二元樹的結(jié)點可以緊湊地存放在一個一維數(shù)組中（性質(zhì)見引

18、理1.2）。第52頁，共74頁，2022年，5月20日，22點36分，星期三53 堆：堆是一棵完全二元樹，它的每個結(jié)點的值至少和（大于或等于）該結(jié)點的兒子們（如果存在的話）的值一樣大（ max-堆）（或小， min-堆）。二分檢索樹：二分檢索樹是一棵二元樹，它或者為空，或者其每個結(jié)點含有一個可以比較大小的數(shù)據(jù)元素，且有：的左子樹的所有元素比根結(jié)點中的元素小；的右子樹的所有元素比根結(jié)點中的元素大；的左子樹和右子樹也是二分檢索樹。注：二分檢索樹要求樹中所有結(jié)點的元素值互異第53頁，共74頁，2022年，5月20日，22點36分，星期三543. 圖 圖由稱之為結(jié)點和邊的兩個集合組成，記為G=（V，E

19、）。其中，是一個有限非空的結(jié)點集合；是結(jié)點對偶的集合，的每一對偶表示的一條邊。第54頁，共74頁，2022年，5月20日，22點36分，星期三55有關(guān)圖的的重要概念無向圖：邊的表示（，）有向圖：邊的表示，成本：帶有成本的圖稱為網(wǎng)絡(luò)鄰接：如果存在邊（i，j）則稱結(jié)點i和j鄰接結(jié)點的度（出度入度）路徑：由結(jié)點vp到vq的一條路（path）是結(jié)點 vp ， vi1 ， vi2 ， ， vim ， vq的一個序 列，它使得( vp ， vi1 ) ，( vi1 ，vi2 ) ， ， ( vim ， vq )是E（G）的邊。路的長度：組成路的邊數(shù)。第55頁，共74頁，2022年，5月20日，22點36分

20、，星期三56簡單路徑：除了第一和最后一個結(jié)點可以相同以外， 其它所有結(jié)點都不同。環(huán)：第一個和最后一個結(jié)點相同的簡單路。連通圖：在無向圖中，如果每對結(jié)點之間都存在一條 路，則稱該圖是連通的。子圖：是由G的結(jié)點集V的子集（記為VB）和邊集E 中連接VB中結(jié)點的邊的子集所組成的圖。連通分圖：一個圖的最大連通子圖。有向圖的強連通性：在有向圖中，如果對于每一對結(jié) 點i和j，既存在一條從i到j(luò)的路，又存在一條從j 到i的路，則稱該有向圖是強連通的。第56頁，共74頁，2022年，5月20日，22點36分，星期三57圖的表示方法鄰接矩陣 鄰接表第57頁，共74頁，2022年，5月20日，22點36分，星期三

21、581.5 遞歸和消去遞歸遞歸 一個算法若其中有調(diào)用自身的過程，則稱該算法是一個遞歸算法。 遞歸是一種強有力的設(shè)計方法 遞歸的效率問題第58頁，共74頁，2022年，5月20日，22點36分，星期三59 例1.3 斐波那契(Fibonacci)序列： F0 = F1 = 1 Fi = Fi-1 + Fi-2 （i1) 算法1.7 求斐波那契數(shù) procedure F(n) /返回第n個斐波那契數(shù)/ integer n if n= 1 then return(1) else return(F(n-1) + F(n-2) endif end F算法效率：對F(n-1) 、F(n-2)存在大量的重復(fù)

22、計算改 進：保存中間結(jié)果第59頁，共74頁，2022年，5月20日，22點36分，星期三60練習(xí)題18Procedure F1(n) If n2 then return(1) Else return (F2(2,n,1,1) EndifEnd F1Procedure F2(i,n,x,y) If i=n Then call F2(i+1,n,y,x+y) Endif Return(y)End F2第60頁，共74頁，2022年，5月20日，22點36分，星期三61練習(xí)17題假設(shè)t(n)是所給出的F(n)的時間函數(shù)，證明t(n)=O(2n-2)第61頁，共74頁，2022年，5月20日，22點3

23、6分，星期三62練習(xí)18題以下是計算第n個斐波那契數(shù)的函數(shù)Procedure F1(n)If(nb / if b=0 then return(a) else return (GCD(b,a mod b) endif end GCD 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;第63頁，共74頁，2022年，5月20日，22點36分，星期三64例1.5 遞歸在非數(shù)值算法設(shè)計中的應(yīng)用 已知元素x，判斷x是否在A（1：n）中。 算法1.9 在A（1：n）中檢索x procedure SEARCH(i) /如果在A（1：n）/中有一元素A（k）=

24、x，則將其第一次出現(xiàn)的下標(biāo)k返回，否則返回0/ global n,x,A(1:n) case :in: return(0) :A(i) = x; return(i) :else: return(SEARCH(i+1) endcase end SEARCH第一次調(diào)用ans-SEARCH(1)第64頁，共74頁，2022年，5月20日，22點36分，星期三652. 消去遞歸直接遞歸的消去規(guī)則： 基本思路：將遞歸過程中出現(xiàn)遞歸調(diào)用的地方，用等價的非遞歸代碼來代替，并對return語句做適當(dāng)處理。 13條規(guī)則：處理直接遞歸調(diào)用中的遞歸代碼和return語句，將之轉(zhuǎn)換成等價的迭代代碼。 初始化 在過程的

25、開始部分，插入說明為棧的代碼并將其初始化為空。在一般情況下，這個棧用來存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。 將標(biāo)號L1附于第一條可執(zhí)行語句。然后對于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來代替。第65頁，共74頁，2022年，5月20日，22點36分，星期三66 處理遞歸調(diào)用語句 將所有參數(shù)和局部變量的值存入棧。 棧頂指針可作為一個全程變量來看待。 建立第i個新標(biāo)號Li，并將i存入棧。這個標(biāo)號的i值將用來計算返回地址。 此標(biāo)號放在規(guī)則所描述的程序段中。 計算這次調(diào)用的各實在參數(shù)（可能是表達式）的值，并把這些值賦給相應(yīng)的形式參數(shù)。 插入一條無條件轉(zhuǎn)向語句轉(zhuǎn)向過程的開始部分：

26、Goto L1第66頁，共74頁，2022年，5月20日，22點36分，星期三67 對遞歸嵌套調(diào)用的處理 如果這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將中建立的標(biāo)號附于這條語句上。 如果此過程不是函數(shù)，則將中建立的標(biāo)號附于所產(chǎn)生的轉(zhuǎn)移語句后面的那條語句。 以上步驟實現(xiàn)消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return語句進行處理（純過程結(jié)束處的end可看成是一條沒有值與之聯(lián)系的return語句）。第67頁，共74頁，2022年，5月20日，22點36分，星期三68 對每個有return語句的地方，執(zhí)行下述規(guī)則： 如果棧為空，則執(zhí)行正常返回。 否則，將所有輸出參數(shù)（帶有返回值的出口參數(shù)， out/inout型）的當(dāng)前值賦給棧頂上的那些對應(yīng)的變量。 如果棧中有返回地址標(biāo)號的下標(biāo)，就插入一條此下標(biāo)從棧中退出的代碼，并把這個下標(biāo)賦給一個未使用的變量。 從棧中退出所有局部變量和參數(shù)的值并把它們賦給對應(yīng)的變量。 如果這個過程是函數(shù)，則插入以下指令，這些指令用來計算緊接在return后面的表達式并將結(jié)果值存入棧頂。 用返回地址標(biāo)號的下標(biāo)實現(xiàn)對該標(biāo)號的轉(zhuǎn)向。第68頁，共74頁