算法分析(复习版).doc

分治法：将一个复杂的问题分解成若干个规模较小、相互独立，但类型相同的子问题求解；然后再将各子问题的解组合成原始问题的一个完整答案，这样的问题求解策略就叫 分治法快速排序算法，归并排序算法，二分搜索算法，还有汉诺塔问题等都是用分治法求解的。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若个规模较小、相互独立且与原问题类型同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题解。最大最小元问题 在一个元素集合中寻找最大元素和最小素的问题，即 在互不相同的 n个数 x 1 , x2 ,xn 中，找出最大和最小的数。二分搜索 在有序表（已按关键字值非减排序）中搜索给定元素的问题。条件：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。二叉判定树 二分搜索过程的算法行为可以用一棵二叉树来描述。通常称这棵描述搜索算法执行过程的二叉树为二叉判定树分治法求解排序问题思想 ：按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。合并排序和快速排序是两种典型的符合分治策略的排序算法。合并排序：把两个或多个有序序列合并成一个有序序列。 两路合并排序 最好时间复杂度： O(nlogn ) 最坏时间复杂度： O(nlogn ) 平均时间复杂度：O(nlogn ) 辅助空间： O(n ) 快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是 ：在待排序的序列（K0 ,K1, K n-1 )中选择一个元素作为 分划元素，也称为主元。不妨假定选择K( 处于位置j)为主元。经过一趟特殊的分划处理将原序列中的元素重新排列，使得以主元为轴心，将序列分成左右两个子序列。主元左侧子序列中所有元素都不大于主元，主元右侧子序列中所有元素都不小于主元。 最好时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn ) 最坏时间复杂度：O(n2) 辅助空间：O(n )或O(logn)合并排序VS快速排序1、问题分解过程：合并排序 将序列一分为二即可。快速排序 需调用Partition函数将一个序列划分为子序列。2、子问题解合并得到原问题解的过程：合并排序 需要调用 Merge函数来实现。（Merge函数时间复杂度为 O(n）快速排序 一旦左、右两个子序列都已分别排序，整个序列便自然成为有序序列。（异常简单，几乎无须额外的工作，省去了从子问题解合并得到原问题解的过程）选择问题是指在 n 个元素的集合中，选出某个元素值大小在集合中处于第 k 位的元素，即所谓的求第k小元素问题。 矩阵相乘 矩阵用二维数组存储，相乘的时间复杂度为 (n 3 ) 分治法的思想 分治法在 每一层递归 上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。 贪心法是通过 分步决策的方法来求解问题的。贪心法每一步上用作决策依据的选择准则被称为最优量度标准（局部最优解） 。在根据最优量度标准选择分量的过程中，还需要使用一个 可行解判定函数 可行解判定函数 ( 约束条件) 。贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。贪心法一般具有 2 个重要的性质：贪心选择性质 和 最优子结构性质 。贪心选择性质：是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的 第一个基本要素，也是贪心算法与动态规划算法的主要区别。最优子结构性质：一个问题的最优解包含其子问题的最优解。问题的最优子结构性质是该问题可用动态规划算法 或 贪心算法求解的关键特征 。背包选择最优量度标准选取单位重量价值最大的物品装包 , 即每次选 p i / w i 最大的物品装包标准最合理 ,得到最优解.(正确性有待证明)基本步骤 :1 、首先计算每种物品 单位重量的价值 Pi/ Wi 并按非增次序进行排序；2 、然后依 贪心选择策略，选择 单位重量价值最高的物品 装入背包。依此策略一直地进行下去，将尽可能多的物品全部装入背包，直到将背包装满。3 、若装入某件物品时， 不能全部装下 ，而背包内的物品总重量仍未达到 W ，则根据背包的剩余载重，选择单位重量价值次高的物品并尽可能多地装入背包。最佳合并模式两路合并外排序算法通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将n个长度不等的有序子文件合并成一个有序文件。 合并n个有序子文件成为一个有序文件的合并过程可以有多种方式，称为 合并模式 。 在整个合并过程中，需从外存读写的记录数最少的合并方案称为 最佳合并模式两路合并最佳模式问题的 最优量度标准为带权外路径长度最小 。最小代价生成树一个无向连通图的 生成树 生成树 是一个极小连通子图，它包括图中全部结点，并且有尽可能少的边。一棵 生成树的代价 生成树的代价 是树中各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的 最小代价生成 最小代价生成树。最优量度标准选择使得迄今为止已入选 S 中边的代价之和增量最小的边。普里姆算法的贪心准则是：在保证 S 所代表的子图是一棵树的前提下选择一条最小代价的边 e=( u,v ) 。克鲁斯卡尔算法的贪心准则是：按边代价的非减次序考察 E 中的边，从中选择一条代价最小的边 e=( u,v ) 。Prim 算法 ：由于Prim 算法中每次选取的边两端总是一个已连通顶点和一个未连通顶点，故这个边选取后一定能将该未连通点连通而又保证不会形成回路。因此每选择一条边后， 无须再判断边集Se 是否包含回路 。设G=(V,E)是带权连通图，F=(U,S)是正在构造中的生成树。Prim算法的基本步骤是：1、从U=v0,S=开始构造，其中v0V是任选顶点；2、然后作如下的贪心选择：在所有一个端点u在生成树上(uU)、而另一个端点不在生成树上(vV-U)的边中选择最小权值边。3、按照上述选边准则，选取n-1条最小边加到生成树上。当U=V时,T=(V,S)是G的一棵最小代价生成树。Kruskal 算法 ：为了确保最终得到生成树，每选择一条边时，都 需要判定边集 Se 是否包含回路 。克鲁斯卡尔算法描述：设G=(V,E)是带权连通图，F=(U,S)是正在构造中的生成树。初始时，U=V,S=。选边的准则：在E中选择一条最小权值边(u,v),并从E中删除；若在S代表的子图中加入边e=(u,v)后不形成回路，则将其加入S。其含义，u和v不在森林F的同一棵树上，当边(u,v)加入S后, 这两棵树合并成一棵树。当S中包含n-1条边时，F=(V,S)就是图G的一棵最小代价生成树。比较Prim算法和Kruskal算法Prim算法：保证S所代表的子图是一棵树的前提下，选择一条最小代价的边e=(u,v);Kruskal算法：构造生成树的过程中,边集S代表的子图不一定是连通的;按边代价的非减次序考察E中的边，从中选择一条代价最小的边e=(u,v);Prim算法：由于Prim算法中每次选取的边两端总是一个已连通顶点和一个未连通顶点，故这个边选取后一定能将该未连通点连通而又保证不会形成回路。因此每选择一条边后，无须再判断边集S e是否包含回路。Kruskal算法：为了确保最终得到生成树，每选择一条边时，都需要判定边集Se是否包含回路。 一个问题能够使用贪心策略的条件如下： 问题的解是向量结构 具有最优子结构特性 能够获取最优量度标准 能证明是最优解 动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似 。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被 重复计算 ，动态规划法解决这 种子问题重叠现象 。贪心法要求针对问题设计最优量度标准 ，但这在很多情况下并不容易 。 动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，可以处理不具备贪心准则 的问题。贪心法求解问题的每一步上根据最优量度标准做出某种决策，产生 n- 元组解的一个分量。用于决策的贪心准则仅依赖于局部的和以前的选择，但 不依赖于尚未做出的选择和 子问题的解 。而动态规划法每一步的决策 依赖于子问题的解 。为了在某一步上做出选择，需要先求解若干子问题，再根据子问题的解做出决策，这就是动态规划法求解问题的 自底向上的 方法。动态规划法与分治法共同点：将待求解的问题 分解成若干子问题 ，先求解子问题，然后再从这些子问题的解得到原问题的解不同点：1 、适合于用 动态规划法 求解的问题，分解得到的各 子问题往往 不是相互独立的 ；而 分治法中子问题相互独立 。2 、 动态规划法 用表保存已求解过的子问题的解，再次碰到同样的 子问题 时 不必重新求解 ，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而 分治法 中对于每次出现的子问题均求解，导致同样的子问题 被 反复求解 ，故产生指数增长的时间复杂度，效率较低。动态规划法与贪心法共同点：都是求解 最优化问题 ；都要求问题具有 最优子结构性质 。不同点：1 、求解方式不同：动态规划法：自底向上 ；贪心法：自顶向下 。以 迭代的方式 作出 相继的贪心选择 ， 每作一次贪心选择就将所求问题简化为一个规模更小的子 问题。 2 、对子问题的依赖不同： 动态规划法：依赖于各子问题的解 ，所以只有在解出相关 子问题后 , 才能作出选择；应使各子问题最优，才能保证整 体最优； 贪心法：不依赖于子问题的解。仅在当前状态下作出最好 选择， 即 局部最优选择 ，然后再去解作出这个选择后产生 的相应的子问题。一个最优化多步决策问题是否适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。找关键活动的目的：重视关键活动；对关键活动投入较多的人力和物力，确保工程按期完成。缩短整个工期：关键活动对缩短整个工期起着至关重要的作用；非关键活动对缩短整个工期不起作用。贪心法和动态规划法它们的解都被表示成一个 n- 元组 (x 0 ,x 1 , ,x n-1 ), 其中每个分量 x i 的值取自某个集合 S i ，所有允许的元组组成一个候选解集。Kruskal 所有边 ; 0/1 背包问题 (x 0 ,x 1 , ,x n-1 )问题描述中给出用于判定一个候选解是否是可行解的约束条件 ( 边上两个顶点不在同一棵树上 ; 0/1 背包问题中的背包载重量 ) 。回溯法要求问题的解向量具有 n- 元组 ( x1 ,x 2 , xn ) 的形式，每个解分量 xi从一个给定的集合 S i 取值。显式约束：规定每个 xi取值的约束条件。（显式约束规定了问题的 候选解集 解空间）对于问题的一个实例，解向量满足 显式约束条件 的所有多元组，构成了该实例的一个 解空间 。通常情况下, 回溯法的求解目标是在状态空间树上找出满足约束条件的所有可行解.隐式约束 ：给出了判定一个候选解是否为 可行解 的条件。为满足问题的解而对不同分量之间施加的约束。 目标函数（代价函数）：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的最优解 。状态空间树 ：描述问题解空间的树形结构。 树中每个结点称为一个 问题状态 ； 若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态 ； 若从根到某个解状态的路径代表一个 可行解 元组，则该解状态为 答案状态 ； 如果求解的是最优化问题 ，还要用 目标函数 衡量每个答案结点，找出其中目标函数取最优值的最优答案结点 。回溯法 适用于 解一些 组合数相当大 的问题。回溯法 ：在求解的过程中，以 深度优先方式 逐个 生成 状态空间树中结点，求问题的 可行解 或 最优解 。为提高搜索效率，在搜索过程中用 约束函数 和 限界函数（统称 剪枝函数 ）来剪去不必要搜索的子树，减少问题求解所需 实际生成 的状态空间树结点数，从而避免无效搜索。回溯法和分枝限界法使用剪枝函数的 深度优先 生成状态空间树中结点的求解方法称为回溯法；使用剪枝函数的广度优先生成结点的求解方法称为分枝限界法 。分枝限界法的基本做法是：以 广度优先 的方式搜索问题的状态空间树。每一个活结点只有一次机会成为E- 结点。按照广度优先原则，活结点一旦成为E-结点R后，就依次生成它的所有孩子 结点。在这些孩子结点中，导致 不可行解 或导致非最优解的孩子结点 被舍弃 ，其余孩子结点被一一加入活结点表中。然后 R自身成为死结点，从活结点表中取下一结点成为当前 E- 结点 ，重复上述结点扩展过程,直到找到所需的解或活结点表为空时为止。分枝限界法与回溯法的异同分枝限界法与回溯法的共同点都是在问题的状态空间树上搜索 问题解的算法。都用活结点表实现，都可用 约束函数 剪去不含答案结点的分枝,都可用限界函数 剪去不含最优解