昆明理工大学-算法分析与设计-期末复习资料

算法设计与分析期末复习资料邹华宇201210405204第一部分基础知识（44分，共12题）第二部分算法编程（56分，用C程序设计语言或者伪代码描述算法）考点一时间复杂度的判断（比较大小）课本P17—P22基本概念算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。一个算法所耗费的时间等于算法中每条语句的执行时间之和。设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。基本运算就是可以用来衡量算法运行时间的主要运算。常见算法时间复杂度：常数阶O(1)：表示算法的运行时间为常量线性阶O(n)：表示该算法是线性算法对数阶O(log2n)：二分搜索算法线性对数阶O(nlog2n)：快速排序算法平方阶O(n2)：对数组进行排序的各种简单算法，例如直接插入排序的算法立方阶O(n3)：做两个n阶矩阵的乘法运算指数阶O(2n)：求具有n个元素集合的所有子集的算法O(n!)：求具有n个元素的全排列的算法算法分析中常见的复杂度：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)O(nn)随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。算法分析中，记号O表示渐进上界，记号Ω表示渐进下界，记号Θ表示紧渐进界。计算算法时间复杂度方法：1.一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))分析：随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。2.在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T(n)的同数量级（它的同数量级有以下：1，log2n，n，nlog2n，n2，n3，2n，n!），找出后，f(n)=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n)=O(f(n))3.容易计算的方法是：看看有几重for循环，没有循环的复杂度是常数，一层循环的复杂度是O(n)，两层循环的复杂度是O(n2)，依此类推；如果有二分则为O(logn)，二分例如快速幂、二分查找；如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。算法的渐进时间复杂性的含义：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是实用时间复杂度相差的常熟倍，因此可以用T(n)的数量级评价算法。时间复杂度T(n)的数量级称为渐进时间复杂性。使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O(1)，在最坏情况下，搜索的时间复杂性为O(logn)。考题：（3分）下面程序段的所需要的计算时间为O(n2)。For(inti=1;i=n;i++){For(j=0;i=n;j++){S[i][j]=0;For(k=0;k=n;k++)S[i][j]+=a[i][j]*b[i][j];}}考点二算法的基本概念课本P1-P5程序是算法用某种程序设计语言的具体实现。算法是指解决问题的一种方法或一个过程。算法是由若干条指令组成的有穷序列，且要满足输入输出，确定性，可行性和有穷性四条性质。算法必须满足有穷性，程序不一定满足有穷性。算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。算法设计的质量指标：正确性，简明性，高效性，最优性。算法分析的目的是分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。考点三动态规划算法课本P103动态规划最短路径，求最小权（课本例题）（12分）动态规划算法适用于解具有某种最优性质问题。动态规划是解决多阶段决策过程最优化的一种方法。动态规划算法的基本要素为最优子结构性质与子问题重叠性质。最优子结构性质的含义是问题的最优解包含其子问题的最优解。动态规划算法中，通常不同子问题的个数随问题规模呈多项式级增长。解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是回溯法，不需要排序的是动态规划和分支限界法。动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。可以用动态规划算法解决的问题：矩阵连乘问题，建立递归关系，求最优解，0/1背包问题等。简述动态规划法的基本思想。为了节约重复求相同子问题的时间，引入一个表（数组），不管它们是否对最终解有用，把新的子问题的解答存于该表中，待以后遇到同样子问题时，就不再重复求该子问题，而直接从表中取出该子问题的解答，这就是动态规划法所采用的基本思想。简述动态规划解决问题的主要步骤。（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。简述动态规划方法所运用的最优化原理。“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k(1kn)，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。简述最优子结构性质。一道动态规划问题其实就是一个递推问题，假设当前决策结果是f[n]，则最优子结构就是要让f[n-k]最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质。动态规划算法为什么需要最优子结构性质？最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构。例题：一个有7个顶点的有向连通图，请求出顶点1到顶点7的最短路径,写出你的计算过程。考点四贪心算法课本P138给一个具体值，用贪心法求出最优解，要有过程（考查背包问题）（10分）贪心算法总是做出在当前看来最优的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。贪心算法的基本要素为最优子结构性质与贪心选择性质。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择达到。选择能产生最优解的贪心准则是设计贪心算法的核心问题。可以用贪心算法解决的问题：背包问题，单源最短路径，最小生成树问题等。贪心算法与动态规划算法的的相同点和不同之处：同：贪心算法和动态规划算法都要求问题具有最优子结构性质；异：贪心具有贪心选择性质，这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。简述贪心算法的基本思想。是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。例题：有0-1背包问题如下：n=6，M=20，P=（11，8，15，18，12，6），W=（5，3，2，10，4，2）。其中n为物品个数，M为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。解：P=（18，15，12，11，8，6），W=（10，2，4，5，3，2）单位重量物品价值（1.8，7.5，3，2.2，2.67，3）1.先把重量为2的物品放进背包，此时剩余载重量为18，P为15；2.把重量为2的物品放进背包，此时剩余载重量为16，P为21；3.把重量为4的物品放进背包，此时剩余载重量为12，P为33；4.把重量为3的物品放进背包，此时剩余载重量为9，P为41；5.把重量为5的物品放进背包，此时剩余载重量为4，P为52；由于104，所以不能完全放进背包。放满需要重量4，P为1.8*4+52=59.2。总价值最大为59.2。考点五递归算法课本P21递归问题改为非递归问题（课本例题）（10分）递归算法是直接或间接地调用自身的算法。递归函数是用函数自身给出定义的函数。递归函数的二要素是边界条件与递归方程。在分治法中，使子问题规模大致相等的做法是出自一种平衡子问题的思想。出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。简述分治法的基本思想。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法所能解决的问题一般具有哪几个特征？请简述。（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。为什么用分治法设计的算法一般有递归调用？子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。考点六回溯法课本P152回溯法是指具有限界函数的深度优先生成法。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。常见的两种分支限界法为队列式与优先队列式。队列式(FIFO)分支限界法：按照队列先进先出原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架。用回溯法解0/1背包问题时，该问题的解空间结构为子集树结构。用回溯法解批处理作业调度问题时，该问题的解空间结构为排列树结构。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。简述回溯法基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的搜索特点是什么？在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。分支限界法的搜索策略是什么？在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。用分支限界法设计算法的步骤。根据所解问题确定解结构；确定解空间树；以广度优先搜索搜索解空间，并在搜索过程中用剪枝函数避免无效搜索