《算法复习1.docx》由会员分享，可在线阅读，更多相关《算法复习1.docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date算法复习1算法复习1重要概念关于算法与复杂度1. 算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。算法是解决某类问题的一系列运算的集合，算法是指解决问题的一种方法或一种过程。程序是算法用程序设计语言的具体实现。2. 算法重要特性是什么？确定性、可行性、输入、输出、有穷性（输入、输出、确定性、有限性）3. 算法分析的目的是什么？分析算法占用计
2、算机资源的情况，对算法做出比较和评价，设计出更好的算法。4. 算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。算法的时间复杂性指算法中 元数据 的执行次数。通常可以通过计算循环次数、基本操作频率、计算步。5. 计算机的资源最重要的是 时间 和 空间 资源。因而，算法的复杂性有 时间复杂度 和 空间复杂度 之分。6. 设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。7. 分治算法的时间复杂性常常满足如下形式的递归方程： 其中，g(n)表示将规模为n的问题分解为子问题以及组合相应的子问题的解所
3、需的时间 。7、算法的时间复杂性与问题的什么因素相关？算法的时间复杂性与问题的规模相关，是问题大小n的函数。8、 算法的渐进时间复杂性的含义？当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。9、 最坏情况下的时间复杂性和平均时间复杂性有什么不同？最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n，I) , IDn平均时间复杂性
4、是所有输入实例的处理时间与各自概率的乘积和：A(n) =P(I)T(n，I) IDn10、记号O表示（渐进上界）， 记号表示（渐进下界）， 记号表示（紧渐进界）记号O的定义正确的是O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) ；记号的定义正确的是 (g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；a) 以下关于渐进记号的性质是正确的有：（A）A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. b)对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或或，并简
5、述理由。（12分）(1) (2) (3) （1），（2），（3）c)用O、表示函数f与g之间阶的关系f(n)= g(n)= ?答案： 阶的关系： f(n)=(g(n)算法与基本思想1、 简单描述分治法的基本思想。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。2. 贪心算法的基本思想？3. 简述动态规划方法所运用的最优化原理。“
6、最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。4. 简单描述回溯法基本思想。回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在搜索过程中，逐步构造出状态
7、空间树，即边搜索，边构造。5. prim算法的基本思想。思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。6. 阐述归并排序的分治思路。讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。7. 快速排序的基本思想是什么。快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分
8、成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。快排的性能取决于划分的对称性8. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。9. 简述二分检索（折半查找）算法的基本过程。设输入是一个按非降次序排列的元素表Ai：j 和x，选取A(i+j)/2与x比较
9、，如果A(i+j)/2=x，则返回(i+j)/2，如果A(i+j)/2x，则Ai：(i+j)/2-1找x，否则在A (i+j)/2+1：j 找x。上述过程被反复递归调用。10. 背包问题的目标函数和贪心算法最优化量度相同吗？11. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。12. 何谓最优子结构性质？某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。13. 采用回溯法求解的问题，其解如何表示？有什么规定？问题的解可以表示为n元组：（x1,x2,xn），xiSi, Si为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（
10、x1,x2,xi）(in)一定合理。14. 回溯法的搜索特点是什么？既带有系统性，又带有跳跃性在解空间树上跳跃式地深度优先搜索，即用判定函数考察xk的取值，如果xk是合理的就搜索xk为根节点的子树，如果xk取完了所有的值，便回溯到xk-1。15. n皇后问题回溯算法的判别函数place的基本流程是什么？将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。16. 为什么用分治法设计的算法一般有递归调用？子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。17. 为什么要分析最坏情况下的算法时间复杂性？最坏情况下的时间复杂
11、性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性有可操作性。18. 简述渐进时间复杂性上界的定义。T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，nNo，有T(n)f(n)，这种关系记作T(n)=O(f(n)19. 二分检索算法最多的比较次数？log2n20. 快速排序算法最坏情况下需要多少次比较运算？最坏情况下快速排序退化成冒泡排序，需要比较n2次21. 回溯法的解（x1,x2,xn）的隐约束一般指什么？回溯法的解（x1,x2,xn）的隐约束一般指个元素之间应满足的某种关系22. 贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选
12、择来达到23. 最优子结构性质: 问题的最优解包含了其子问题的最优解24. 回溯法: 具有限界函数的深度优先生成法用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)回溯法的效率不依赖于以下哪一个因素？（C ）A. 产生xk的时间；B. 满足显约束的xk值的个数；C. 问题的解空间的形式； D. 计算上界函数bound的时间；E. 满足约束函数和上界函数约束的所有xk的个数。F. 计算约束函数constraint的时间；回溯法的算法框架
13、按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。旅行售货员问题的解空间树是（排列树）。25. 分治算法的基本步骤包括 分解，递归，组合 。26回溯算法的基本思想是 在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝） 。27动态规划和分治法在分解子问题方面的不同点是 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的 。28贪心算法中每次做出的贪心选择都是 局部 最优选择。 29随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 不同 的结果。-