资源描述：
《算法设计与分析考试答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1．算法的渐进时间复杂度分析，能够对给定的代码段（伪代码段）进行时间复杂度分析，能够对用关于问题规模n的函数表示的时间复杂度计算其渐进阶。
2．概念1)算法:算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤2)递归算法:递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数来表示问题的解3)可行解:满足某线性规划所有的约束条件的任意一组决策变量的取值，都称为该线性规划的一个可行解4)解空间:如果ξ1,ξ2,...ξs是一般齐次线性方程组的s个解,则它们的任一线性组合c1ξ1+c2ξ2+...+csξs也是该齐次线性方程组
2、的解向量.由此可知若齐次线性方程组有非零解,则其解有无穷多个,而齐次线性方程组所有解的集合构成一个向量空间,这个向量空间就称为解空间.解空间也就是一个集合5)目标函数:在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。6)最优解:使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。7)最优化问题:主要是指以下形式的问题：给定一个函数，寻找一个元素使得对于所有A中的，（最小化）；或者（最大化）。8)子问题:就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把
3、子问题分成更小的子问题9)分治法:就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并10)贪心法:在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解11)动态规划:虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法12)备忘录算法:备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归
4、方式是自顶向下的，而动态规划算法则是自底向上的。13)回溯法:回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标1)贪心选择性质:是指所有问题的整体最优解可以通过一系列局部最优解的选择,即贪心选择来达到2)最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质3)重叠子问题:在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次.这些被反复计算的子问题就是重叠子问题.3．分治法的算法框架
DividAndConquer(p(n))//分治法设计原理{if(n<=n0)returnA
5、dhoc(p(n));else{//将P分解为较小的子问题P1、P2、…、PkDividepintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=DividAndConquer(pi);//递归解决PireturnMerge(y1,y2,...,yk);//合并子问题}} 其中p(n)表示一个规模为n的问题P，可以把它分解成k个规模较小的子问题，这些问题相互独立，并且与原来的问题结构相同。在解决这些子问题时，又用相同的方式对每一个子问题进行进一步的分解，直到某个阈值n0为止。递归的解这些子
6、问题，再把各个子问题的解合并起来，就得到原来问题的解。这就是分治法的思想方法。n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。Adhoc(p(n))是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法Adhoc(p(n))求解。 4．贪心法的步骤
(1)建立数学模型来描述问题。 (2)把求解的问题分成若干个子问题。 (3)对每一子问题求解，得到子问题的局部最优解。 (4)把子问题的解局部最优解合成原来解问题的一个解。5．贪心法的基本要素
(1)贪心选择性质(2)最优子
7、结构性质6．动态规划的步骤
(1)找出最优解的性质,并刻画其结构特征(2)递归的定义最优解(3)以自底向上的方式计算出最优值(4)根据计算最优值时得到的信息,构造出最优解7．动态规划的基本要素
(1)最优子结构(2)重叠子问题8．贪心法与动态规划的比较
动态规划法和贪心法都要求问题具有最优子结构性质,这是两类算法的一个共同点。动态规划法和贪心法的基本区别在于,贪心法仅产生一个判定序列，而动态规划法可能产生许多判定序列，但是按照最优原理，包含非局部最优的部分序列的结果肯定不可能是最优的，所以不予考虑。9.备忘录算法与动态规划算法的比较动态规划算法的一
8、个变形是备忘录方法。与动态规划算法一样，备忘录方法用一个表格来保存已解决的子问题的答案，在再碰到该子问题时，只要简单地查看
