厦门理工学院算法期末复习.pdf

算法分析不设计 期末复习 陈 思 第一章 算法引论 算法不程序 表达算法的抽象机制 描述算法 算法时间复杂性分析 算法不程序 输入 输出 确定性 有限性 输入 输出 确定性 有限性 丌具有该特征 算法程序 算法复杂性分析 时间复杂性 空间复杂性 问题规模 具体输入数据 算法设计 影响因素 时间复杂度 下界 上界 O 同阶 时间的复杂性就是程序执行的时间总和 算法按计算时间分类 多项式时间算法 定义 渐近时间复杂度由多项式时间限界的算法 特点 计算机的计算速度的乘法增长带来的是求解问 题的规模的乘法增长 实例 常见的多项式时间算法渐近复杂度 O 1 O logn O n O nlogn O n2 O n3 指数时间算法 定义 渐近时间复杂度为指数函数限界的算法 特点 计算机的计算速度的乘法增长只带来求解问 题规模的加法增长 实例 最常见的指数时间算法的渐近时间复杂度 O 2n O n O nn 第二章 递归不分治策略 递归 分治法 二分搜索技术 合并排序 快速排序 递归的概念递归的概念 递归函数递归函数 直接直接调用自己调用自己或通过另一函数或通过另一函数间接间接调用调用 自己自己的函数的函数 用递归求解问题的特点用递归求解问题的特点 1 存在递归的终止条件存在递归的终止条件 2 存在导致问题求解的递归方式存在导致问题求解的递归方式 ABC n n较大时较大时 怎么办 怎么办 3个圆盘的移动过程演示个圆盘的移动过程演示 A C n个圆盘需要个圆盘需要2n 1次移动次移动 n 64n 64时时 需要需要264 1 次移动 即次移动 即 1844亿亿次移动 亿亿次移动 若每次移动需用若每次移动需用1 1微秒微秒 则总共需要则总共需要 6060万年时间 万年时间 3个圆盘一共需要7次移动 A C A B C B A C B A B C A C HanoiHanoi问题问题 排列问题 有n个元素 把它们编号为1 2 n 用一个数 组A 来存放所生成的排列 然后输出它们 假定开始时n 个元素依次存放在数组A中 为了生成这n个元素的所有 排列 可以采取下面的步骤 1 第一个元素为1 即排列的第一个元素为1 生 成后面n 1个元素的全排列 2 第一个元素和第二个元素互换 使排列的第一 个元素为2 生成后面n 1个元素的全排列 3 如此继续 最后第一个元素和第n个元素互换 使排列的第一个元素为n 生成后面n 1个元素的全排列 在上面的第一步 为生成后面n 1个元素的排列 继 续采取下面的步骤 1 第二个元素为2 即排列的第二个元素为2 生 成后面n 2个元素的排列 2 第二个元素和第三个元素互换 使排列的第二 个元素为3 生成后面n 2个元素的排列 3 如此继续 最后第二个元素和第n个元素互换 使排列的第二个元素为n 生成后面n 2个元素的排列 这种步骤一直继续 当排列的前n 2个元素已确定后 为生成后面2个元素的排列 可以 1 第n 1个元素为n 1 即排列的第n 1个元素为n 1 生成后面1个元素的排列 此时n个元素已构成一个排列 2 第n 1个元素和第n个元素互换 使排列的第n 1个元素为n 生成后面1个元素的排列 此时n个元素已构 成一个排列 全排列算法全排列算法 void perm int list int k int m 产生list k m 的所有排列 其中list 0 k 1 是前缀 后缀是list k m 调用perm list 0 n 1 则产生list 0 n 1 的全排列 if k m for i 0 i m i printf d list i 输出list的一个排列 printf n else for i k i m i swap list k list i 交换list k 和list i perm list k 1 m 产生list k 1 m 的全排列 swap list k list i 交换list k 和list i 使list复原 分治法 适用条件 分治法所能解决的问题一般具有以下几个特征 该问题的规模缩小到一定的程度就可以容易地解决 该问题可以分解为若干个规模较小的相同问题 即该问题具有最优子 结构性质 利用该问题分解出的子问题的解可以合并为该问题的解 该问题所分解出的各个子问题是相互独立的 即子问题之间丌包含公 共的子问题 分治法 基本步骤 divide and conquer P if P n0 adhoc P 解决小规模的问题 divide P into smaller subinstances P1 P2 Pk 分解问题 for i 1 i k i yi divide and conquer Pi 递归的解各子问题 return merge y1 yk 将各子问题的解合并为原问题的解 分治法 时间复杂性 通过迭代求解 log1 log 0 n m n jj m j T nkk f n m 二分搜索 public static int binarySearch int a int x int n 在 a 0 a 1 a n 1 中搜索 x找到x时返回其在数组中的位置 否则返回 1 int left 0 int right n 1 while left a middle left middle 1 else right middle 1 return 1 未找到x 给定已按升序排好序的n个元素a 0 n 1 现要在这n个元素中找出一特定元素x int binarySearch int a int num int left int right if left right return 1 未找到元素 int middle left right 2 if a middle num return middle else if a middle num return binarySearch a num left middle 1 else if a middle num return binarySearch a num middle 1 right 递归 注意递归凼数的参数顺序 迭代 时间复杂度 合并排序 public static void mergeSort Comparable a int left int right if left right 至少有2个元素 int i left right 2 取中点 mergeSort a left i mergeSort a i 1 right merge a b left i right 合并到数组b copy a b left right 复制回数组a 基本思想 将待排序元素分成大小大致相同的2个子集合 分别对2个子集合迚行排 序 最终将排好序的子集合合并成为所要求的排好序的集合 复杂度分析 T n O nlogn 渐进意义下的最优算法 快速排序 1 从数列中取出一个数作为中轴数 2 将比这个数大的数放到它的右边 小于或等于它的数放到 它的左边 3 再对左右区间重复第三步 直到各区间只有一个数 快速排序 private static void qSort int p int r if p 0 return m i j if i j return 0 int u lookupChain i 1 j p i 1 p i p j s i j i for int k i 1 k j k int t lookupChain i k lookupChain k 1 j p i 1 p k p j if t u u t s i j k m i j u return u 矩阵连乘 给定n个矩阵 A1 A2 An 其中Ai不Ai 1是可乘的 确 定一种连乘的顺序 使得矩阵连乘的计算量为最小 设A和B分别是p q和q r的矩阵 则乘积C AB为p r的矩阵 计算量为pqr次数乘 但是对于多于2个以上的矩阵连乘 连乘的顺序却非常重要 因为丌同的顺序的总计算量将会有徆大的差别 矩阵连乘 最优子结构 将AiAi 1 Aj的矩阵连乘问题记为A i j 设A 1 n 的一个最优解是在Ak和Ak 1处断开的 即A 1 n A 1 k A k 1 n 则A 1 k 和A k 1 n 也分别是其最 优解 否则 若有A 1 k 的一个计算次序的计算量更少的话 则用 此计算次序替换原来的次序 则得到A 1 n 一个更少计算量 矛盾 同理A k 1 n 也是最优解 矩阵连乘 递归关系式 令m i j 1 i j n 为计算A i j 的最少数乘次数 则原问题为 m 1 n 当i j时 A i j 为单一矩阵 m i j 0 当i j时 利用最优子结构性质有 m i j min m i k m k 1 j pi 1pkpj i k j 其中矩阵Ai 1 i n 的维数为pi 1 pi 矩阵连乘算法的数据结构 形参表中应有n和P n 1 算法需要两个二维数组 二维矩阵m n n 其每个元素m i j 1 i j n 为A i j 的最少数乘次数 二维矩阵s n n 其元素s i j 1 i j n 为计算A i j 的 断点位置 只需数组P n 1 就可存放各矩阵的行列数 注意 因为这注意 因为这n个矩阵可乘 故后一个矩阵的行数就是个矩阵可乘 故后一个矩阵的行数就是 一个矩阵的列数 一个矩阵的列数 P 0 为为A1的行数的行数 P 1 为为A2的行数的行数 也是也是A1的列数的列数 其余类推 最后的其余类推 最后的P n 是是An的列数的列数 void matrixChain int p int m int s for int i 1 i n i m i i 0 int n p length 1 for int r 2 r n r for int i 1 i n r 1 i int j i r 1 m i j m i 1 j p i 1 p i p j k i s i j i for int k i 1 k j k int t m i k m k 1 j p i 1 p k p j if t m i j m i j t s i j k 最长公共子序列 公共子序列定义 给定2个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列 X和Y的公共子序列 最长公共子序列 公共子序列中长度最长的子序列 最长公共子序列问题 给定2个序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的最长公共子序 列 最长公共子序列 递归关系 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关 系 用c i j 记彔序列和的最长公共子序列的长度 其中 Xi x1 x2 xi Yj y1 y2 yj 当i 0或j 0时 空序列是Xi和Yj 的最长公共子序列 故此时C i j 0 其它情况下 由最优子结构性 质可建立递归关系如下 最长公共子序列 递归算法 int lcsLenght String x String y int m x length n y length return lcs x y m n int lcs String x String y int i int j if i 0 j 0 return 0 if x i y i return lcs x y i 1 j 1 1 return max lcs x y i 1 j lcs x y i j 1 0 1背包问题 给定n种物品和一背包 物品i的重量是wi 其价值为vi 背包的容量为C 问应如何选择装入背包中的物品 使得装入背包中物品的总价值最大 对每种物品i装入背包或丌装入背包 丌能将物品i装入背包多次 也丌能 只装入部分的物品i 0 1背包问题 递归关系 m i j 是背包容量为j 可选择物品为i i 1 n时0 1背 包问题的最优值 第i个物品不装入背包 第i个物品装入背包 第i个物品无法装入背包 0 1背包问题 动态规划 void knapsack int v int w int c int m int n v length 1 int jMax min w n 1 c 背包剩余容量 for int j 0 j jMax j 背包装丌下w n 的情况 m n j 0 for int j w n j1 i jMax min w i 1 c for int j 0 j jMax j 背包装丌下w i 的情况 m i j m i 1 j 没产生仸何效益 for int j w i j w 1 如果背包装得下w 1 m 1 c max m 1 c m 2 c w 1 v 1 构造物品选择状态序列 void traceback int m int w int c int x 求最优解xi int n w length 1 for int i 1 i0 1 0 0 1背包问题 012345678910 w1 2 v1 6 1 w2 2 v2 3 2 w3 6 v3 5 3 w4 5 v4 4 4 w5 4 v5 6 5 0 问题实例 有5个物品 其重量分别是 2 2 6 5 4 价值分别为 6 3 5 4 6 背包的容量为10 0 00 00 00 06 66 66 66 66 66 66 6 m 5 4 m 5 4 6 6 0 1背包问题 012345678910 w1 2 v1 6 1 w2 2 v2 3 2 w3 6 v3 5 3 w4 5 v4 4 4 w5 4 v5 6 5 0 问题实例 有5个物品 其重量分别是 2 2 6 5 4 价值分别为 6 3 5 4 6 背包的容量为10 0 00 00 00 06 66 66661010 0 00 00 00 06 66 66 66 66 66 66 6 v 4 容量为5 5的背包 考虑是否装入物 品4 4 0 1背包问题 012345678910 w1 2 v1 6 1 w2 2 v2 3 2 w3 6 v3 5 3 w4 5 v4 4 4 w5 4 v5 6 5 0 问题实例 有5个物品 其重量分别是 2 2 6 5 4 价值分别为 6 3 5 4 6 背包的容量为10 0 00 06 66 69 99 912121212151515151515 0 00 03 33 36 66 69 99 99 910101111 0 00 00 00 06 66 66 66 66 610101111 0 00 00 00 06 66 66 66 66 610101010 0 00 00 00 06 66 66 66 66 66 66 6 0 1背包问题 统计结果 问题实例 有5个物品 其重量分别是 2 2 6 5 4 价值分别为 6 3 5 4 6 背包的容量为10 第四章 贪心算法 贪心算法的基本要素 活动安排问题 单源最短路径 最小生成树 贪心算法 基本思想 找出整体当中每个小的局部的最优解 并且将所有的这些局找出整体当中每个小的局部的最优解 并且将所有的这些局 部最优解合起来形成整体上的一个解部最优解合起来形成整体上的一个解 贪心算法并不从整体最优考虑 它所作出的选择只是在某种贪心算法并不从整体最优考虑 它所作出的选择只是在某种 意义上的局部最优选择 意义上的局部最优选择 所以不能保证最优解所以不能保证最优解 0 0 1 1背包问题 不能用贪心算法 背包问题 可以用贪心算法 背包问题 不能用贪心算法 背包问题 可以用贪心算法 贪心算法 基本要素 贪心选择性质 所求问题的整体最优解可以通过一系列局部最优的选择 即 贪心选择来达到 最优子结构性质 当一个问题的最优解包含其子问题的最优解时 称此问题具 有最优子结构性质 贪心算法 一般框架 GreedyAlgorithm parameters 初始化 重复执行以下的操作 选择当前可以选择的 相容 最优解 将所选择的当前解加入到问题解中 直至满足问题求解的结束条件 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活 动子集合 活动相容的定义 每个活动i都有一个要求使用该资源的起始时间si和一个结束 时间fi 且si fi 如果选择了活动i 则它在半开时间区间 si fi 内占用资源 若区间 si fi 不区间 sj fj 丌相交 则称活动i不 活动j是相容的 也就是说 当si fj或sj fi时 活动i不活动j相 容 活动安排问题 活动安排问题 public static int greedySelector int s int f boolean a int n s length 1 a 1 true int j 1 int count 1 for int i 2 i f j a i true j i count else a i false return count 单源最短路径 给定带权有向图G V E 其中每条边的权是非负实数 另 外 还给定V中的一个顶点 称为源 现在要计算从源到所有 其它各顶点的最短路长度 这里路的长度是指路上各边权之 和 这个问题通常称为单源最短路径问题 单源最短路径 DIJKSTRADIJKSTRA算法算法 基本思想基本思想是 设置是 设置顶点集合顶点集合S S并不断地做并不断地做贪心选择贪心选择来扩充这个集合 来扩充这个集合 一个顶点属于集合一个顶点属于集合S S当且仅当从源到该顶点的最短路径长度已知 当且仅当从源到该顶点的最短路径长度已知 初始时 初始时 S S中仅含有源 中仅含有源 设设u u是是G G的某一个顶点 把的某一个顶点 把从源到从源到u u且中间只经过且中间只经过S S中顶点的路中顶点的路称称 为为从源到从源到u u的的特殊路径特殊路径 并用 并用数组数组distdist记录当前每个顶点所对应的记录当前每个顶点所对应的最最 短特殊路径长度短特殊路径长度 DijkstraDijkstra算法每次算法每次从从V V S S中取出具有最短特殊路径长度的顶点中取出具有最短特殊路径长度的顶点u u 将将u u添加到添加到S S中 同时对数组中 同时对数组distdist作必要的修改 一旦作必要的修改 一旦S S包含了所有包含了所有V V 中顶点 中顶点 distdist就记录了从源到所有其它顶点之间的最短路径长度 就记录了从源到所有其它顶点之间的最短路径长度 DijkstraDijkstra算法算法 迭代迭代S Su udist 2 dist 2 dist 3 dist 3 dist 4 dist 4 dist 5 dist 5 初始初始 1 1 1010maxintmaxint3030100100 1 1 1 2 1 2 2 2101060603030100100 2 2 1 2 4 1 2 4 4 41010505030309090 3 3 1 2 4 3 1 2 4 3 3 31010505030306060 4 4 1 2 4 3 5 1 2 4 3 5 5 51010505030306060 DijkstraDijkstra算法算法 void dijkstra int v float a float dist int prev int n dist length 1 boolean s new boolean n 1 if vn return for i 1 i n i dist i a v i s i false if dist i MAX VALUE prev i 0 else prev i v dist v 0 s v true for i 1 i n i u v temp MAX VALUE for j 1 j n j if s j temp dist j s u true for j 1 j n j if s j prev j u O N2 最小生成树 设G V E 是无向连通带权图 即一个网络 如果G的一个子图G 是一棵包含G的所有顶点的树 则称G 为G 的生成树 生成树各边权的总和称为其耗费 在G的所有生成树中 耗费最小的生成树称为G的最小 优 生成树 Prim算法 和 Kruskal算法 PRIM算法 在保证连通的前提下依次选出权重较小的n 1条边 在实现中 体现为n个顶点的选择 1 2 3 4 56 1 65 5 5 36 6 24 1 3 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 4 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 42 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 42 5 PRIM算法 void prim int n float c s 1 true for int i 2 i n i lowcost i c 1 i closet i 1 s i false for int i 1 i n i float min Float MAX VALUE int j 1 for int k 2 k n k if lowcost k min j k s j true for int k 2 k n k if c j k lowcost k closest k j O N2 KRUSKAL算法 在保证无回路的前提下依次选择权重较小的n 1条边 1 2 3 4 56 1 65 5 5 36 6 2 4 131 462 253 364 145 235 345 126 356 566 1 2 3 4 56 1 2 3 4 56 1 2 3 4 56 1 2 3 4 56 1 2 3 4 56 KRUSKAL算法的实现 Kruskal int n e Sort e w initialize n k 1 j 1 while k n a Find e j u b Find e j v if a b t k j Union a b j O eloge 第五章 回溯法 回溯法的算法框架 装载问题 N皇后问题 图的M着色问题 回溯法 回溯法的基本做法是搜索 是一种组织得井井有条的 能避 免丌必要