算法分析TheAnalysisofAlgorithmsppt課件

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

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

3、非降序列數(shù)組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)先查找鄰接矩陣表示，該遍歷算法的時(shí)間效率屬于(|V|2)鄰接鏈表表示，該遍歷算法的時(shí)間效率屬于(|V|+|E|).

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

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

6、=0./19俄式乘法(Multiplication la russe)兩個(gè)大整數(shù)m和n乘法n * m=n2* 2 * mn為偶數(shù)n * m=n -12* 2 * m + mn為奇數(shù)./20約瑟夫斯問題(Josephus)在約瑟夫斯環(huán)中最后的幸存者是誰？偶數(shù)情況：J(2k)=2J(k)-1奇數(shù)情況：J(2k+1)=2J(k)+1二進(jìn)制表示：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)問題描畫給定一個(gè)含有n個(gè)元素的(或叫關(guān)鍵字)的集合，確定集合中第k小的元素。A(0)A(1)A(j-1)A(j)A(j+1)A(n-2)A(n-1)V劃分元素kj時(shí)，第k小元素所在的集合K=j時(shí)，第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調(diào)用劃分函數(shù)兩個(gè)新的子問題T(n)=T(n/2)+(n+1)./24插值查找(Interpolation search)有序數(shù)組查找的另一種方法由直線方程可得：鍵值比較次數(shù)小于log2log2n+1./25二叉樹的查找與插入最差效率(n)，平均效率(logn)./26拈游戲(Nim Game)有13根火柴棍，每次最少拿走1根，最多能拿走4根，拿走最后一根火柴的就是贏家。該如何拿走火柴？n=m+1實(shí)例是敗局m+2n 2m+1是勝局2m+2=2(m+1)另一個(gè)敗局獲勝戰(zhàn)略每次拿走n mod (

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

10、可以從頂至下遞歸，也可以從底至上非遞歸的來運(yùn)用。減治法有三種變種：1)減去一個(gè)常量2)減去一個(gè)常數(shù)因子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