45_算法设计与分析.pptx

算法设计与分析基础 Introduction to the Design and Analysis of Algorithms;第5 章 减治法;★ 算法策略 减治法：利用给定规模与较小规模问题解之间的关系求解问题的方法。实现 —— 自顶向下：规模减小（递归） 自底向上：规模增大（非递归） 减常量法：常量通常为1（减 1 法） 减常因子法：常因子通常为 2（减半法）;★ 插入排序;折半插入法 —— 组合利用减一法和减半法;· 插入排序效率分析;★ 深度优先搜索DFS (Depth-First Search);· 许多图的算法要求对图进行遍历或周游(graph traversal). 主要两种 DFS (Depth-First Search) , BFS (Breadth-First Search) .;· DFS 算法过程图示（以树为例）;· DFS 栈过程图示;· DFS树与森林;· DFS 递归版;· DFS 时间效率分析;二、图的邻接链表表示：下一个邻接顶点在链表中是 确定的;· DFS 简单应用;· BFS 队列过程图示;· BFS 非递归算法;· BFS 相关讨论;★ 拓扑排序 ( Topological Sort );· 有向无环图 无向图：仅有 2 种类型的边 —— 树边、回边有向图：可有 4 种类型的边;· 拓扑排序算法;DFS解拓扑排序 【例2】7 个任务的安排;★ 生成组合对象;· 减一算法（实现 —— 从底向上，规模增加） 在 { 1, ... , n-1 } 排列中，可以 从左向右 或 从右向左 插入 n较好的插入法：（有什么好处？）;· 生成幂集;· 减一算法（实现 —— 自底向上，规模加一） 从空集开始，每次向已生成的每个子集中加入一个元素，如此继续，直到所有 n 个元素都加入为止。;· 子集的比特串表示 每个比特（二进制位）表示 有、无 两种状态：1 － 有，0 － 无例如：集合A = { a1, a2, a3 } ，3 个比特表示 23 = 8 个子集;★ 减常因子法;· 时间效率分析;· 减常因子法算例 —— 俄式乘法（俄国农夫法）;· 俄式乘法过程举例;★ 减可变规模法;· 中值查找算法;· 减治法查找中值过程例;· 插值查找 —— 减可变规模法算例;;· 二叉查找树（Binary Search Tree, BST）;· BST 插入算法（生成BST）;· BST 删除算法;寻找替换节点（举例说明）： 被删节点值37;· BST 算法效率（查找、插入、删除效率类型相同）;★ 作业：算法设计与分析基础 Introduction to the Design and Analysis of Algorithms;第5 章 减治法;★ 算法策略 减治法：利用给定规模与较小规模问题解之间的关系求解问题的方法。实现 —— 自顶向下：规模减小（递归） 自底向上：规模增大（非递归） 减常量法：常量通常为1（减 1 法） 减常因子法：常因子通常为 2（减半法）;★ 插入排序;折半插入法 —— 组合利用减一法和减半法;· 插入排序效率分析;★ 深度优先搜索DFS (Depth-First Search);· 许多图的算法要求对图进行遍历或周游(graph traversal). 主要两种 DFS (Depth-First Search) , BFS (Breadth-First Search) .;· DFS 算法过程图示（以树为例）;· DFS 栈过程图示;· DFS树与森林;· DFS 递归版;· DFS 时间效率分析;二、图的邻接链表表示：下一个邻接顶点在链表中是 确定的;· DFS 简单应用;· BFS 队列过程图示;· BFS 非递归算法;· BFS 相关讨论;★ 拓扑排序 ( Topological Sort );· 有向无环图 无向图：仅有 2 种类型的边 —— 树边、回边有向图：可有 4 种类型的边;· 拓扑排序算法;DFS解拓扑排序 【例2】7 个任务的安排;★ 生成组合对象;· 减一算法（实现 —— 从底向上，规模增加） 在 { 1, ... , n-1 } 排列中，可以 从左向右 或 从右向左 插入 n较好的插入法：（有什么好处？）;· 生成幂集;· 减一算法（实现 —— 自底向上，规模加一） 从空集开始，每次向已生成的每个子集中加入一个元素，如此继续，直到所有 n 个元素都加入为止。;· 子集的比特串表示 每个比特（二进制位）表示 有、无 两种状态：1 － 有，0 － 无例如：集合A = { a1, a2, a3 } ，3 个比特表示 23 = 8 个子集;★ 减常因子法;· 时间效率分析;· 减常因子法算例 —— 俄式乘法（俄国农夫法）;· 俄式乘法过程举例;★ 减可变规模法;· 中值