算法分析期末重点.docx

算法与程序l 算法是解决问题的一种方法或一个过程，是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序是算法用某种程序设计语言的具体实现，可以不满足算法的性质。l 算法分析 质量 正确性、可靠性、健壮性、可读性 效率 时间复杂度、空间复杂度算法复杂性分析 -时间和空间 算法复杂性 = 算法所需要的计算机资源的量 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 n是问题的规模（输入大小）分治与递归l 递 归 优点：结构清晰，可读性强，容易用数学归纳 法来证明算法正确性。因此它为设计算法、调试程序带来很大方便。缺点：递归算法运行效率较低，时空消耗大。l 分治法的设计思想是：将一个难以直接解决的大问题， 分割成一些规模较小的独立相同问题，递归地解子问题， 将子问题的解合并得到原问题的解，分而治之。l 分治特征该问题的规模缩小到一定的程度就可以容易地解决； 分而可解 该问题可以分解为若干个规模较小的相同问题;（具有最优子结构）分而相同分解出的子问题的解可以合并为原问题的解； 分而可合分解出的各个子问题是相互独立的。 分而独立l 二分搜索技术给定已按升序排好序的n个元素a0:n-1，在这n个元素中，找出一特定元素x。时间复杂性为 O(logn) 。算法思想：分成个数大致相同的两半，取an/2与x比较，若找到则算法终止，若x an/2，在数组a左半部继续搜索xl 合并排序& 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。& 最坏时间复杂度：O(nlogn)& 平均时间复杂度：O(nlogn)& 辅助空间：O(n)l 快速排序基本思想: 记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。基本步骤：分解:以ap为基准将数组ap:r分成3段，ap:q-1中任何一个元素小于等于aq,而aq+1:r中任何一个元素小于等于aq,下标q在划分过程中确定。递归求解：通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。合并：当ap:q-1和aq+1:r就地排好序之后，ap:r就已排好序了。& 最坏时间复杂度：O(n2)& 平均时间复杂度：O(nlogn)& 辅助空间：O(n)或O(logn)l 线性时间选择找出第k小的元素基本思路：分解问题、缩小规模输入数组进行递归划分，利用快速排序思想、每次递归处理部分子数组将元素分组并排序，找出每组的中位数，再找最后的中位数（有两个选较大的那个）利用中位数，构造线性时间复杂度的算法基本步骤：数组ap:r划分成两个子数组，使ap:i中的每一个元素都不大于ai+1:r中的每一个元素。计算子数组ap:i的元素个数j，若k=j，则第k小元素在子数组ap:i中，否则在ai+1:r，此时第k小元素是该数组的第k-j小元素。用随机划分函数法下，最坏情况下 时间O(n2)，平均时间 O(n)。改进：在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。 利用中位数构造平衡子动态规划l 动态规划算法的基本要素 最优子结构性质 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这 种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首 先假设由问题的最优解导出的子问题的解不是最优的，然后再 设法说明在这个假设下可构造出比原问题最优解更好的解，从 而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问 题的最优解逐步构造出整个问题的最优解。最优子结构是问题 能用动态规划算法求解的前提。 重叠子问题性质 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时 间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动 态规划算法只需要多项式时间，从而获得较高的解题效率。l 设计动态规划算法的步骤 找出最优解的性质，并刻划其结构特征 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解动态规划方法是处理分段过程最优化问题的一类极其有效的方法。最优化原则指出，多阶段过程的最优决策序列应当具有性质： 无论过程的初始状态和初始决策是什么， 其余的决策都必须相对于初始决策所产生的状态 构成一个最优决策序列。（最优子结构性质）l 基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次解决方法：保存已解决的子问题的答案，在需要时再找出 已求得的答案，就可以避免大量重复计算，从而得到多项 式时间算法。l 最大子段和问题描述：给定长度为n的整数序列，a1.n, 求 1,n某个子区间i,j使得ai+aj和最大。或者 求出最大的这个和。递推式：最后得到的bf就是最大子字段和sum，则af就是末元素，求以af为末元素的字段和，当与sum大小相同时就看可以记录首元素了。最长公共子序列 m行n列矩阵Cij计算最长公共子序列的长度，bij记录由哪个子问题的解得到的。l 0-1背包问题问题描述：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大贪心算法l 贪心算法的基本要素 最优子结构性质整体的最优解包含子问题的最优解 贪心选择性质整体的最优解可通过局部最优解达到；每次选择依赖于当前，不依赖于之后做法 要确定一个具体问题是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。l 基本思想：将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体的最优解l 算法优点 求解速度快,时间复杂性有较低的阶. 算法缺点 需证明是最优解.l 解题思路建立数学模型来描述问题。 把求解的问题分成若干个子问题。 对每一子问题求解，得到子问题的局部最优解。 把子问题的解局部最优解合成原来解问题的一个解l 贪心算法与动态规划算法的异同共同点:都要求问题具有最优子结构性质。 不同点：动态规划算法通常以自底向上的方式解各子 问题，而贪心算法则通常以 自顶向下的方式进行，以 迭代的方式作出相继的贪心选择，每作一次贪心选择 就将所求问题简化为规模更小的子问题。l 背包问题算法思路1).将各物体按单位价值由高到低排序.2).取价值最高者放入背包. 3).计算背包剩余空间. 4).在剩余物体中取价值最高者放入背包. 若背包剩余容量=0或物体全部装入背包为止l 0-1背包（动态规划）和背包问题（贪心算法 背包问题可以装入物品的部分）对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征l 哈夫曼编码算法思路： 1)以n个字母为结点构成n棵仅含一个点的二叉树集合,字母的频率 f 即为结点的权 2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树:增加一个根结点将这两棵树作为左右子树.新树的权为两棵子树的权之和. 3) 反复进行步骤2)直到只剩一棵树为止.算法分析：HuffmanTree初始化优先队列Q需要O(n) DeleteMin和Insert需O(logn). n-1次的合并总共需要O(nlogn) 所以n个字符的哈夫曼算法的计算时间为O(nlogn)l 单源最短路径：问题: 给定带权有向图G=(V,E), 其中每条边的权是一个非负实数.要计算从V的一点v0(源)到所有其他各顶点的最短路长度. 路长指路上各边权之和。算法思想(Dijkstra) :设最短路长已知的终点集合为S,初始时 v0S, 其最短路长为0,然后用贪心选择逐步扩充S :每次在V-S中 ,选择路径长度值最小的一条路径x加入s生成从v0到所有其他结点的最短路径的贪心方法就是按照路径长度的非降次序生成这些路径。l 最小生成树：算法思路: 首先置S=1, T= .若SV, 就作如下的贪心选择：选取满足条件iS, jV-S,且cij最小的边(i, j),将顶点j添加到S中边(i, j)添加到T中.这个过程一直进行到S=V时为止. T中的所有边构成G的一棵最小生成树回溯法具有限界函数的深度优先生成法称为回溯法l 基本思路：有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井 条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。l 解题思路在解空间树中，按深度优先策略，从根结点出发搜索解空间树。 算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯； 否则，进入该子树，继续按深度优先策略搜索解题步骤：针对所给问题，定义问题的解空间 确定易于搜索的解空间结构 以深度优先方式搜索解空间，并在搜索过程用剪枝函数避免无效搜索用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树l 回溯法的算法框架：递归回溯迭代回溯子集树和排列树子集树：通常有2n个叶节点，结点总个数为2(n+1)-1,遍历子集树的时间O（2n）排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。 排列树通常有n!个叶子节点。因此遍历排列树需要O(n!)的计算时间案列分析:1.装载问题 2.n后问题 3.0-1背包问题 4.最大团问题 5.图的着色问题 6.旅行售货员问题 分支界限法l 基本步骤： 针对所给问题，定义问题的解空间 确定易于搜索的解空间结构 以广度优先方式搜索解空间 找出所要的解l