算法设计与分析基础第2版清华出版社ch5减治法

《算法设计与分析基础第2版清华出版社ch5减治法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章减治法主要内容：5.1插入排序5.2深度优先查找与广度优先查找5.3拓扑排序5.4生成组合对象的算法5.5减常因子算法5.6减可变规模算法2021/9/141LingJie/GDUT减治法的基本思想将规模为n的问题递减为规模为n-1或n/2的子问题,反复递减后对子问题分别求解,再建立子问题的解与原问题的解的关系。减治法有三个变形:减常数(如1):每此迭代规模减小n→n-1减因子(如1/2):每此迭代规模减半n→n/2减可变规模:每此迭代减小的规模不同2021/9/142LingJie/GDUT5.1插入排序插入排序的过程类似玩牌时整理手中纸牌的过程。它的基本思想是：每步将一个

2、待排序的对象按照其关键字的大小，插到前面已经排好序的序列中的适当位置，直到全部对象插入完毕为止。常用的插入排序有：直接插入排序、折半插入排序、链表插入排序和希尔排序，它们划分的依据是在排好序的序列中寻找插入位置所使用方法的不同。2021/9/143LingJie/GDUT直接插入排序伪代码ALGORITHMInsertionSort(A[0..n-1])//对给定序列进行直接插入排序//输入：大小为n的无序序列A//输出：按非递减排列的序列Afori←1ton-1dotemp←A[i]j←i-1whilej≥0andA[j]>tempdoA[j+1]←A[j]j←j–1A[j+1]

3、←temp2021/9/144LingJie/GDUT直接插入排序举例待排序序列{89,45,68,90,29,34,17}插入过程:{89}不需比较{45,89}{45,68,89}{45,68,89,90}{29,45,68,89,90}{29,34,45,6889,90}{17,29,34,45,68,89,90}插入次数=n-1=6比较次数=?2021/9/145LingJie/GDUT直接插入排序效率分析基本操作:比较比较次数C(n):最坏的情形,每次插入需比较已插入的所有元素,此时,第i次插入比较i个元素,故2021/9/146LingJie/GDUT5.2深度优先和广

4、度优先查找1、深度优先查找可以从任何顶点开始访问图的顶点，每次迭代时，处理与当前顶点相邻的未访问顶点。用栈来跟踪深度优先查找的操作最方便。2021/9/147LingJie/GDUTDFS的伪代码（1）PseudocodeforDepth-first-searchofgraphG=(V,E)：DFS(G)count:=0未访问的顶点标记为0foreachvertexv∈Vdoifv的标记为0dfs(v)dfs(v)count:=count+1顶点v标记为countforeachvertexwadjacenttovdoifwismarkedwith0dfs(w)2021/9/148L

5、ingJie/GDUTDFS的伪代码（2）ALGORITHMDFS(G)//对给定图使用深度优先搜索进行遍历;//输入：图的邻接表表示结点个数为N;//输出：各个结点输出顺序数组fori←0toN-1doVisitArray[i]←0//访问数组初始为0count←0fori←0toN-1doifVisitArray[i]=0dfs(V)//调用子函数dfs进行深度优先遍历dfs(V)//使用深度优先搜索对邻接表进行遍历//输入：结点V的邻接表;//输出：各个结点输出顺序数组count←count+1;VisitArray[V]←count//记录访问的次序tmp←V.linkwh

6、iletmp≠NulldoifVisitArray[tmp.vertex]≠0dfs(tmp.vertex)2021/9/149LingJie/GDUT深度优先举例abefcdgh一个DFS输出序列：a-b-g-c-d-h-f-e2021/9/1410LingJie/GDUT深度优先搜索的效率与图的表示有关对邻接矩阵表示的图：遍历的效率为Θ(V2)对邻接链表表示的图：遍历的效率为Θ(V+E)2021/9/1411LingJie/GDUT2、广度优先查找可以从任何顶点开始访问图的顶点，每次迭代时，处理所有与当前顶点相邻的未访问顶点。用队列来跟踪广度优先查找的操作较方便。

7、2021/9/1412LingJie/GDUTBFS的伪代码（1）BFS(G)count:=0标记每个顶点v=0foreachvertexv∈Vdobfs(v)bfs(v)count:=count+1标记v=count初始化顶点序列vwhile序列非空doa:=frontofqueueforeachvertexwadjacenttoadoifwismarkedwith0count:=count+1markwwithcountaddwtotheendofthequeue