算法分析TheAnalysisofAlgorithmsppt課件

1、算法分析與設計 Analysis and Design of Computer Algorithms第五章 減治法Decrease and Conquer楊春明西南科學技大學計算機學院./2教學內容減治法的普通方法及變種插入排序深度優(yōu)先查找和廣度優(yōu)先查找生成組合對象的算法減常因子算法減可變規(guī)模算法要求掌握減治法的根本思想及在常見問題問題中的運用。./3減治法減治技術利用了一種關系：一個問題給定實例的解和同樣的問題較小實例的解之間的關系。一旦建立了這種關系，就可以從頂至下遞歸，也可以從底至上非遞歸的來運用。減治法有三種變種：1)減去一個常量2)減去一個常數

2、因子3)減去的規(guī)模是可變的./4減一治技術規(guī)模為n的問題規(guī)模為n-1的子問題子問題的解原始問題的解f(n)=anf(n)=f(n-1)*a n1f(n)=a n=1./5減半治技術規(guī)模為n的問題規(guī)模為n/2的子問題子問題的解原始問題的解an=(an/2)2 n是偶數an=(a(n-1)/2)2 *a n是奇數an =a n=1./6插入排序For j2 to n do 將A(j)放到已分類集合A(0.j-1)的正確位置上Repeat算法 InsertionSort(A0.n-1)/用插入排序對給定數組排序/輸入：一個可排序數組/輸出：

3、非降序列數組Afor i1 to n-1 do vAi; ji-1; while (j0 and Ajv) Aj+1Aj; jj-1; Aj+1v;89 | 45 68 90 29 34 1745 89 | 68 90 29 34 1745 68 89 | 90 29 34 1745 68 89 90 | 29 34 1729 45 68 89 90 | 34 1729 34 45 68 89 90 | 1717 29 34 45 68 89 90 ./7深度優(yōu)先查找鄰接矩陣表示，該遍歷算法的時間效率屬于(|V|2)鄰接鏈表表示，該遍歷算法的時間效率屬于(|V|+|E|).

4、/8./9廣度優(yōu)先查找鄰接矩陣表示，該遍歷算法的時間效率屬于(|V|2)鄰接鏈表表示，該遍歷算法的時間效率屬于(|V|+|E|)./10./11廣度優(yōu)先查找./12DFS與BFS的主要性質./13拓撲排序(Topological sorting)有向圖./14拓撲排序(Topological sorting)./15拓撲排序(Topological sorting)./16生成陳列(Permutations)生成由n

5、個元素 a1,a2,.,an的陳列算法 JohnsonTrotter(n)/生成n個數的陳列/輸入：一個正整數n/輸出：1,.,n的一切的陳列數將第一個陳列初始化為12.nwhile 存在一個挪動整數k do 求最大的挪動整數k 把k和它箭頭指向的相鄰整數互換 調轉一切大于k的整數的方向課后思索：如何按照字典序生成a1a2.an后面的陳列呢？./17生成子集Subset背包問題中如何窮舉出給定物品集合的一切子集？A=a1,a2,.,an=a1,a2,.,an-1 /18假幣問題(Fake-Coin)當n1時，W(n)=W(n/2)+1 , W(1)

6、=0./19俄式乘法(Multiplication la russe)兩個大整數m和n乘法n * m=n2* 2 * mn為偶數n * m=n -12* 2 * m + mn為奇數./20約瑟夫斯問題(Josephus)在約瑟夫斯環(huán)中最后的幸存者是誰？偶數情況：J(2k)=2J(k)-1奇數情況：J(2k+1)=2J(k)+1二進制表示：J(6)=J(1102)=1012=5，J(7)=J(1112)=1112=7./21約瑟夫斯問題(Josephus)？J(n,m)=(J(n-1,m)+m) mod nJ(1,m)=0.mryang

7、.org/22選擇問題(Selection Problem)問題描畫給定一個含有n個元素的(或叫關鍵字)的集合，確定集合中第k小的元素。A(0)A(1)A(j-1)A(j)A(j+1)A(n-2)A(n-1)V劃分元素kj時，第k小元素所在的集合K=j時，第k小元素就是劃分元素./23選擇問題(Selection Problem)Procedure SELECT(A,n,k) integer n,k,m,r,j; m1;rn+1;A(n+1)+; loop jr call PARTITION(m,j) case :k=j:return :kj:rj :else:mj+1 e

8、ndcase repeatEnd SELECT調用劃分函數兩個新的子問題T(n)=T(n/2)+(n+1)./24插值查找(Interpolation search)有序數組查找的另一種方法由直線方程可得：鍵值比較次數小于log2log2n+1./25二叉樹的查找與插入最差效率(n)，平均效率(logn)./26拈游戲(Nim Game)有13根火柴棍，每次最少拿走1根，最多能拿走4根，拿走最后一根火柴的就是贏家。該如何拿走火柴？n=m+1實例是敗局m+2n 2m+1是勝局2m+2=2(m+1)另一個敗局獲勝戰(zhàn)略每次拿走n mod (

9、m+1)根火柴棍./27拈游戲(Nim Game)多堆拈游戲每堆火柴棍的數量不一致，每次拿走火柴棍時可以從恣意一堆中拿走恣意允許數量的火柴棍，甚至可以把一堆都拿光。拿走最后一根火柴的是贏家。1901年，哈佛大學數學教授C.L. Bouton發(fā)現了一個精巧解法：解是基于堆中數量的二進制表示的。b1,b2,.,bi分別是各堆數量的二進制表示；計算它們的二進制數位和忽略進位。當且僅當二進制數位和中包含至少一個1時，為勝局；只包含0時，為敗局。./28減治法小結減治技術利用了一種關系：一個問題給定實例的解和同樣的問題較小實例的解之間的關系。一旦建立了這種關系，就

10、可以從頂至下遞歸，也可以從底至上非遞歸的來運用。減治法有三種變種：1)減去一個常量2)減去一個常數因子3)減去的規(guī)模是可變的用減治法處理的問題有：插入排序，DFS，BFS，俄式乘法，選擇問題./29referenceJosephus /deensley/mathdl/Joseph.htmllibrary.wolfram/examples/josephusproblem//deensley/DiscreteMath/flash/ch1/sec1_1/josephus.htmlmathworld.wolfram/JosephusProblem.htmlanswers/topic/josephus-problem?cat=technologyNim Gamearchimedes-l