算法复习1汇编

《算法复习1汇编》由会员分享，可在线阅读，更多相关《算法复习1汇编（5页珍藏版）》请在装配图网上搜索。

1、重要概念关于算法与复杂度1. 算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算 。算法是解决某类问题的一系列运算的集合，算法是指解决问题的一种方法或一种过程。程序是算法用程序设计语言的具体实现。2. 算法重要特性是什么？确定性、可行性、输入、输出、有穷性(输入、输出、确定性、有限性)3. 算法分析的目的是什么？分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。4. 算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。算法的时间复杂性指 算法中元数据的执行次数。通常可以通过计算循环次数、基本操作频率、计算步。5. 计算机的资源最重要的是时间 和 空间 资

2、源。因而，算法的复杂性有时间复杂度 和空间复杂度之分。6. 设Dn表示大小为n的输入集合，t(l)表示输入为I时算法的运算时间，p(l) 表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= p(| )t(l )。I Dn7. 分治算法的时间复杂性常常满足如下形式的递归方程：f(n) d, n nf(n) af(n/c) g(n) , n n其中，g(n)表示将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间7、算法的时间复杂性与问题的什么因素相关？算法的时间复杂性与问题的规模相关，是问题大小n的函数。8、算法的渐进时间复杂性的含义？9、最坏情况下的时间复杂性和平均时间复杂

3、性有什么不同?W(n) = max T(n，I) , I Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和:A(n)=刀 PT(n ,1) I Dn10、记号O表示(渐进上界)，记号 表示(渐进下界)，记号 表示(紧渐进界)记号O的定义正确的是O(g(n) = f(n) |存在正常数c和n0使得对所有n no有：0 f(n) cg(n) ；记号的定义正确的是(g(n) = f(n) |存在正常数c和n0使得对所有n no有：0 cg(n)f(n) ；a)以下关于渐进记号的性质是正确的有：(A)A. f(n) (g(n),g(n)(h( n) f(n) (h( n)h(n) O(f(

4、 n)B. f(n)O(g(n),g(n)O(h(n)C. O(f(n )+O(g( n) = O(mi nf(n) ,g( n)d. f(n)O(g( n)g( n)O(f (n)b)对于下列各组函数f(n)和 g(n)，确定 f(n)=O(g(n)f(n)(g(n)，并简述理由。(12 分)(1)2f (n) log n ； g(n)log n 5;(2)f(n) 2n;g( n) 100 n2;(3)f(n) 2n;g( n) 3n;(1)logn2(log n 5)，(2)2n(100n2)，(3)2nc)用O、表示函数f与g之间阶的关系f(n )=log3 ng(n)=log2 n?

5、答案：阶的关系：f(n )=(g( n)或 f(n) (g(n)或(3n)算法与基本思想1、简单描述分治法的基本思想。分治法的基本思想是将一个规模为 n的问题分解为k个规模较小的子问题，这些子问 题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求 出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上 逐步求出原来问题的解。2. 贪心算法的基本思想?3. 简述动态规划方法所运用的最优化原理。“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1

6、, D2,，Dn,如若这个决策序列是最优的，对于任何一个整数k, 1 kn，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当 前状态，即以后的决策 Dk+1, Dk+2,，Dn也是最优的。4. 简单描述回溯法基本思想。回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索， 解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有 问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到 上层父结点，继续下一步深度优先搜索过程。在搜索过程中，逐步构造出状态空间树，即边搜索，边构造。5. prim算法的基本思想。思路是：最

7、初生成树 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比较，如果A(i+j)/2=x ，则返回(i+j)/2 ，

9、如果 A(i+j)/2x ，则 Ai : (i+j)/2-1 找 x,否则在 A (i+j)/2+1: j找x。上述过程被反复递归调用。10. 背包问题的目标函数和贪心算法最优化量度相同吗?11. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。12. 何谓最优子结构性质?某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质13. 采用回溯法求解的问题，其解如何表示？有什么规定？14. 回溯法的搜索特点是什么?既带有系统性，又带有跳跃性在解空间树上跳跃式地深度优先搜索，即用判定函数考察xk的取值，如果xk是合理的就搜索xk为根节点的子树，如果xk取完了所有的值，便回溯

10、到xk-1。15. n皇后问题回溯算法的判别函数place的基本流程是什么？将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false， 测试完毕则返回true。16. 为什么用分治法设计的算法一般有递归调用？子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。17.为什么要分析最坏情况下的算法时间复杂性?18.简述渐进时间复杂性上界的定义。19. 二分检索算法最多的比较次数？log 2n20. 快速排序算法最坏情况下需要多少次比较运算?最坏情况下快速排序退化成冒泡排序，需要比较n2次21. 回溯法的解(X1,X2,xn)的隐约束一般指什么？回溯法的

11、解(X1,X2,xn)的隐约束一般指个元素之间应满足的某种关系22.23.贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到24.25. 最优子结构性质：问题的最优解包含了其子问题的最优解26.27.回溯法：具有限界函数的深度优先生成法用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为0（h（n）回溯法的效率不依赖于以下哪一个因素？（ C）A.B. 产生xk的时间；C.C. 满足显约束的xk值的个数；E.D. 问题的

12、解空间的形式；E. 计算上界函数bound的时间；F. 满足约束函数和上界函数约束的所有xk的个数。I.G. 计算约束函数constraint的时间；回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。旅行售货员问题的解空间树是（排列树）。25.分治算法的基本步骤包括分解，递归，组合。26. 回溯算法的基本思想是在问题的状态空间树上作带剪枝的DFS搜索（或：DFS剪枝）。27. 动态规划和分治法在分解子问题方面的不同点是前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的。28贪心算法中每次做出的贪心选择都是局部最优选择。29 随机算法的一个基本特征是对于同一组输入，不同的运行可能得到 不同的结果。