1、電子課件數據與計算（第4版）Ch4 算法Data and Computation 4Th,CS of ZJU, PHEIChapter 4 算法 AlgorithmCS, ZJU2019.8Overview算法的概念算法的三種結構算法的表示和發現常用算法算法的方法學數據表達和數據結構Data and Computation 4Th,CS of ZJU, PHEIKey chapter理解算法學習程序設計理解計算機解決問題的過程、方法理解計算機方法要求RaptorProject，and representation: Section 4.5Data and Computation 4Th,CS

2、of ZJU, PHEIAlgorithm高納德（Donald EKnuth）圖靈獎獲得者程序設計和算法的先驅通過計算手段，“發現數據中隱藏的精妙規律”他認為：算法就是計算機科學的基礎計算機是藝術品，不是科學Data and Computation 4Th,CS of ZJU, PHEI4.1 intruductionData and Computation 4Th,CS of ZJU, PHEI計算機的解決方法問題提出計算機可運行的程序軟件問題解決程序用計算機語言對算法的描述求解問題的方法步驟算法程序就是算法的實現例子：歐幾里德（Euclid）問題Data and Computation 4

3、Th,CS of ZJU, PHEI24和16的最大公約數是？Step 1：比較A和B，使A B；Step 2：A division B，得余數R（Remender）；Step 3：若C等于0，B就是最大公約數。結束。 否則將A B, BR，重復Step 2、Step3求解步驟=8求兩個正整數A和B的最大公約數（GCD）計算公式其中mod是取余數思考一下？算法的定義算法是求解問題步驟的有序集合，它能夠產生結果并在有限時間內結束Data and Computation 4Th,CS of ZJU, PHEI算法的特性（Donald EKnuth）確定性有窮性有效性可有零個或多個輸入有一個或多個輸

4、出算法的分類算法一般可分成兩大類：數值運算算法非數值運算算法Data and Computation 4Th,CS of ZJU, PHEI算法的范式程序設計范式（Paradigm）不同的語言有不同的實現方案Edsger Wybe Dijkstra程序設計范式的提出者大O表示法算法的性能（1）存儲空間（2）運行時間（主要）算法時間復雜度特殊的表示方法：大O表示法(Big O notation)例如n個數相加，需要執行的次數就是O(n)n個無序數中查找指定的數，運行時間也是O(n)不是精確的運算時間設計算法:“預測最糟糕的情況，做盡可能好的努力”Data and Computation 4Th,

5、CS of ZJU, PHEI幾種典型的大O時間值O(1)，常數時間運算時間是一個常數，如計算函數值的算法時間O(log n)，對數時間如二分查找這類算法，準確表達應該是log2 n。O(n)，線性時間運行時間和參加運算的數據量n成線性關系。O(n2)，平方時間包括選擇法在內的多種排序算法需要的時間。O(nlog n)快速排序的開銷O(n!)，通常計算最短路徑需要的時間Data and Computation 4Th,CS of ZJU, PHEI4.2 算法的三種結構所有的算法（程序）都由三種結構構成順序結構，按照命令出現的先后順序依次執行循環結構，按照設定的條件重復執行一組命令分支結構，根

6、據設定的條件來決定程序的執行方向基本形態表示了算法的邏輯過程，注重過程，so稱為“面向過程”的程序設計Data and Computation 4Th,CS of ZJU, PHEI順序結構A B分支結構Data and Computation 4Th,CS of ZJU, PHEIdo/while結構循環結構While結構 Data and Computation 4Th,CS of ZJU, PHEI4.3 算法的表示和發現算法的表示把算法以某種形式加以表達一個算法的表示可以有不同的方法常用方法自然語言傳統的流程圖結構流程圖偽代碼PAD圖Data and Computation 4Th,C

7、S of ZJU, PHEI算法工具 Raptor自由軟件(https:/)可執行的流程圖賦值Assignment調用子程序Call輸入輸出選擇循環Data and Computation 4Th,CS of ZJU, PHEIRaptorUsing Help數學函數+ - * / MOD Celling Floor Random關系運算 = /= != = =邏輯運算 AND OR NOT 子流程（Subchart），無返回值子程序（Subprocedure），有返回值提示信息 使用” ”Data and Computation 4Th,CS of ZJU, PHEI使用raptor實現歐幾

8、里德GCD算法DemoData and Computation 4Th,CS of ZJU, PHEI求最大公約數的 C 程序#include stdio.hvoid main() int a,b,r,t; scanf(%d%d,&a,&b); if(ab) t=a;a=b;b=t; r=a % b; while(r) a=b; b=r; r=a%b; /* %號為求余 */ printf(最大公約數為%d,b);Data and Computation 4Th,CS of ZJU, PHEI流程圖（Flowchart）Data and Computation 4Th,CS of ZJU, P

9、HEI歐幾里德算法的流程圖常用的流程圖符號偽代碼表示算法偽代碼（Pseudo-code）表示算法的符號系統”專業人員使用自己喜愛的、或準備用于編程的計算機語言，加上英文描述混合而成注意偽代碼中很多表達和程序語言相同或類似，但它不是計算機語言，不能被計算機執行Data and Computation 4Th,CS of ZJU, PHEI例：偽代碼的歐幾里德GCD算法Startinput positive integer a,bif a3, 3N-6條以上的邊的圖都不可能是平面的庫托拉夫斯基證明：任何非平面圖都包含如下子圖中俄一個Data and Computation 4Th,CS of ZJ

10、U, PHEI平面圖測試算法問題：將平面圖的證明條件轉化為算法大O值：O(n6)，100個點需要執行1億次，1000點需要1018！霍普克洛夫特-陶爾揚算法劃分子圖測試圖中的邊數沒有超過歐拉條件允許的數量劃分子圖：子圖內的任意兩個節點之間存在一條通路（含多邊），且移走任何一個節點，圖中節點還是聯通的利用深度優先（ Depth First Search ）的算法，在圖中找到一個“圈”-從一點出發經過幾個節點又回到出發點移走該圈，將圖分成一系列不連接的“橋”- 測試子圖和橋是否一起組成平面圖？如果圈位于平面，那么每一個橋要么在圈內，要么在其外.關鍵：一次深度搜索就可以完成技術Data and Co

11、mputation 4Th,CS of ZJU, PHEI霍普克洛夫特陶爾揚深度優先搜索（DFS）Example（首次論文“平面圖測試的高效算法”長達20頁）下圖是平面圖么，try？Data and Computation 4Th,CS of ZJU, PHEI 2 34 5 6163254右圖：1632541 圈，是一個路徑橋： 43 和 56 為“橋”-是平面圖，大O值為O(n)About Algorithm，DFS 的啟示算法的發現尋找算法也需要找到更好的算法一個更好的算法可能導致一個巨大的技術進步，例如求解問題-可計算性并非一下子就能夠找到算法更別提找到最佳算法了Data and Co

12、mputation 4Th,CS of ZJU, PHEI4.4 算法舉例理解常用的算法進而體會算法的發現、設計，是大多數學習計算機的人所采用的學習方法。4.4.1 基本算法-Self-learning累加(求和)累積求最大值和最小值求數的位數Data and Computation 4Th,CS of ZJU, PHEI4.4.2 迭代（Iteration）這是計算機算法中最常用的算法思路復雜問題化為簡單問題由舊值推導新值的過程Data and Computation 4Th,CS of ZJU, PHEI算法思路是：迭代Iteration基于循環的算法, 例：判斷一個整數是否為素數 算法思

13、路大O值Data and Computation 4Th,CS of ZJU, PHEI遞歸（Recursion）遞歸的必備知識：函數數學中凡此變數中函彼變數者,則此為彼之函數計算機中一段程序代碼，可以被重復調用功能上和數學的函數類似函數調用將參數帶入函數，返回一個結果Data and Computation 4Th,CS of ZJU, PHEI遞歸Recursion：是算法(程序)的自我調用例：求n的階乘。Data and Computation 4Th,CS of ZJU, PHEI遞歸公式遞歸的偽代碼Start Factorial ( n )/ 函數名，將n帶入函數 if n=0 th

14、en return 1/遞歸出口 else return n* Factorial(n-1)/ 遞歸調用EndData and Computation 4Th,CS of ZJU, PHEI4.4.4 排序（Sort）迭代、遞歸的延續應用是將一組原始數據按照遞增或遞減的規律進行重新排列的算法應用廣泛數值排序文本排序規則遞增或遞減，輸出是原數據的重新排列Data and Computation 4Th,CS of ZJU, PHEI常用的排序(Sort)方法選擇法排序把表中最小的數找到并放入第一個位置比較余下的數，找到次小的數放到第二個位置直到對所有數據全部掃描過冒泡法排序（習題4的T12）開始

15、比較相鄰的兩個數，將較小的向前移動，所有數比較完畢，得到最小的數在第一個位置剩下的數，持續這個過程，找到的次小的數排到列表的第二個位置依次類推，直到結束Data and Computation 4Th,CS of ZJU, PHEI選擇法排序有一組6個數2，12，5，56，34，78從大到小排序Data and Computation 4Th,CS of ZJU, PHEI選擇法排序的復雜度如圖，6個元素排序不需要36次大約為15-16次n個數，掃描次數n-1次每次掃描元素依次減少，因此最多為1+2+n -1 n21/2，因此大O值應該為O(n2*1/2)大O表示法省略其中諸如1/2這樣常數部

16、分,所以選擇法的大O值：O(n2)And：大O值是最糟糕情況下的時間開銷Data and Computation 4Th,CS of ZJU, PHEI查找算法從列表中找到某個數的的位置（即索引）兩種基本的方法：順序查找-未排序的數據，O(n) 折半查找-已經排序的數據, O(log n) 二分法，從列表的一半開始Data and Computation 4Th,CS of ZJU, PHEI順序查找的偽代碼Startread Array xinput key /輸入要查找的數keyflag = false/flag為是否找到的標志i=0while( i=right)return “NoFou

17、nd”mid =( left+right)/2/ 計算中間位置的下標if (xmid = key )/ 找到了，返回 return midelse if(xmidkey) / 查找較大的那一半數組return halfSearch(x, key, mid-1, right)else / 查找較小的那一半數組return halfSerch(x, key, left, mid-1)endData and Computation 4Th,CS of ZJU, PHEI比較順序查找-未排序的數據，O(n)折半查找-已經排序的數據, O(log n)例如，列表中有100,000個數，假設比較一次是1秒

18、順序查找最壞的情況是需要100,000秒折半查找只需要log2100,00017秒順序查找需要的時間是折半法的5882倍如果數據量為109，順序查找的開銷是二分法的3300萬倍!因此大O表示法是算法的時間開銷且隨著數據量的增加而增加的-這才是大O表示法的意義所在Data and Computation 4Th,CS of ZJU, PHEI4.4.6 搜索圖圖也是一種數據類型圖模擬一組連接由節點(node)和邊(edge)組成Data and Computation 4Th,CS of ZJU, PHEIExample:Question 1: 從A點出發到B點，有路徑嗎Question 2:從

19、A點出發，到B點有最短的路徑嗎？有向圖和無向圖搜索方法：深度優先（depth first search，DFS）算法的方法學通常認為，算法沒有方法學可資借鑒的某些方法貪心法分治法動態規劃回溯法Data and Computation 4Th,CS of ZJU, PHEI枚舉、蠻力法求解問題把所有可能的解都列出來，找到最后得到結果-窮盡可能這是很多基礎性問題的算法沒有方（辦）法的方（辦）法適用于規模較小、或者復雜度不高的問題。Example：解密，嘗試密碼的各種可能組合Data and Computation 4Th,CS of ZJU, PHEI貪心法經典例子找零錢問題你需要找給顧客N元零錢

20、，你手上有k 面值分別為X1,X2,.Xk的錢，且從大到小排列，為了用最少的零錢湊出N元錢思路先用最大面值的錢，再用次大面值的，一直到最后湊足N元錢。 這個算法就并不能求出最少需要的硬幣數目So：貪心法只能求出一個較優解Data and Computation 4Th,CS of ZJU, PHEI埃及分數Fibonacci算法（1）用b除以a的商的整數部分加上1的值，作為埃及分數的某一個分母c；（2）將a乘以c減去b作為新的a。（3）將b乘以c作為新的b。（4）如果a大于1且能夠整除b，則最后一個分母為b/a。（5）如果a等于1，則最后一個分母為b，否則轉（1）繼續。Try: 7/8=Dat

21、a and Computation 4Th,CS of ZJU, PHEI貪心法 貪心算法（Greedy Algorithm）從小的方案推廣到大的解決方法。 “眼下能拿到就先拿到”求解最優問題一種通用的算法設計技術：可行性每一步選擇必須滿足問題的約束；局部最優它是當前可選擇的方案中最優的；不可取消性選擇一旦做出，在算法的其后步驟中不能被取消。缺點：可能不是最佳解Data and Computation 4Th,CS of ZJU, PHEIExample：背包問題一個貪婪的小偷，帶著有個有限容積的背包，面對3個不同價值和體積的物品，他如何能夠在背包中裝入價值最高的商品組合而背包也能夠放得下？D

22、ata and Computation 4Th,CS of ZJU, PHEI物品價值體積A，筆記本電腦2208B，藝術布罩臺燈1206C，錄音電話機1013解？最優么？只要它能夠滿足設計目標，它仍然具有價值Another Example著名的最短路徑問題(TSP)也沒有最優解如果一個旅行者需要經過n個城市，他的行程如何才能最短這需要用到數學中的組合學，要給出所有的可能路徑，然后得到最短的那一個。如果有5個城市，線路是120條，如果城市增加1倍達到10個，那么需要計算的線路是10！超過300萬條，是5個城市線路的2500倍。O(n!)! - 超大的O值貪心法從出發城市開始，每次選擇下一個城市都

23、是沒有去過、但距離最短的那個城市有意思：這個解的確有意義Data and Computation 4Th,CS of ZJU, PHEI分治法-分而治之何為好算法？算法的優劣都是和效率與速度相關與問題的規模相關分治法（Divide and Conquer）Divide：較大規模的問題分解為若干個較小規模的子問題，找出子問題的解Conquer: 各個子問題的解合并成整個問題的解基于遞歸包含兩個以上的遞歸Data and Computation 4Th,CS of ZJU, PHEIExample：快速排序Quick Sort選擇一個基數，例如第一個數。每個數與基數比較，分小、大兩組對兩組繼續比較

24、分組.合并Data and Computation 4Th,CS of ZJU, PHEI12，56，5，34，2，11，785，2，111256，34，78521112563478Think about: Big O?Question: 哪一種情況下是最糟糕的？歸并排序Merge Sorting將待排序的數分成數量基本相等的兩組，重復分組排序，最后合并Data and Computation 4Th,CS of ZJU, PHEI12，56，5，34，2，11，7812 56 5 34 2 11 7812 56 5 34 2 11 7856 12 34 5 11 2 7856 34 12 5

25、 78 11 278 56 34 12 11 5 2第一次分組：第二次分組：第一次排序：第一次合并：第二次合并：比較快排與歸并排序金塊問題如何從一組數據中找出最大的和最小的有一個老板有一袋金塊，被獎勵優秀雇員金塊：排名第一的雇員將得到袋中最重的金塊排名第二的雇員將得到袋中最輕的金塊如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊假設有一臺比較重量的儀器，我們希望用最少的比較次數找出最輕和最重的金塊Data and Computation 4Th,CS of ZJU, PHEI動態規劃背包問題容積為T的背包，如何能夠在M個不同價值和體積的物品中，選擇使包裝下最大價值的物品N個D

26、ata and Computation 4Th,CS of ZJU, PHEI物品ABCDE體積34789價值45101113如背包體積為17，可裝5件A=價值20，或D、E各1件價值24.問題的名稱來源于如何選擇最合適的物品放置于給定背包中。Data and Computation 4Th,CS of ZJU, PHEI動態規劃（Dynamic Programming）美國數學家（Richard Bellman， 20世紀50 年代）建立、發展的一種解多階段決策問題的優化方法思想一個較大問題被分解為若干個子問題，且子問題具有重疊（不是相互獨立的，不適用分治法）可以將每個子問題的解存放到一個表

27、中，這樣就可以通過查表解決問題另一個例子：斐波那契級數（Fibonacci Numbers）Data and Computation 4Th,CS of ZJU, PHEI回溯法回溯法也叫窮盡搜索法（Brute-Force Search），嘗試分步地去解決一個問題。基本思想在分步解決問題的過程中，當它通過嘗試發現現有的分步答案不能得到有效的、正確的解答的時候，將取消上一步甚至上幾步的計算，再通過其他的可能的分步解答再次嘗試尋找問題的答案。通常使用遞歸實現Data and Computation 4Th,CS of ZJU, PHEI問題回溯法問題1：從N個自然數(1,2,n)中選出r個數的所有

28、組合。問題2：數的劃分: 整數n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7，k=3，下面三種分法被認為是相同的。1，1，5; 1，5，1; 5，1，1;問有多少種不同的分法。問題3：經典問題， n皇后問題。在一個n n的棋盤上放置n個皇后，每行一個并使其不能互相攻擊（同一列、同一行、同一斜行上的皇后都會自動攻擊）。Data and Computation 4Th,CS of ZJU, PHEI數據表達和數據結構算法最終都需要通過適當的數據表達，以便能夠被計算機所處理 - 抽象數據表達是對數據的符號化表示。數據結構的定義包括三方面內容：邏輯結構、存儲結構和對數據的操作按照它的結構形式可以分為鏈、表、堆、隊、樹等Data and Computation 4Th,CS of ZJU, PHEI樹型結構：數據元素存在一對多的關系數據結構數據元素是數據的基本單位,數據元素之間存在某種關聯有三類基本的數據之間的結構Data and Computation 4Th,CS of ZJU, PHEI線性結構：數據元素存在一對一的關系圖狀結構：數據元素存在多對多的關系數據的邏輯關系抽象數類型是一組數學模型（對象）以及定義在該模型上的一組操作數據的邏輯關系如: 整數類型的對象是整數，對象的操作是、用程序設計語言實現相應的抽象數據類型對象邏輯結構的物理實