2023年算法设计与分析期末备考知识点总结

通俗地讲,算法是解决问题的方法，严格地说,算法是对特定问题求解环节的一种描述，是指令的有限序列。算法还必须满足一下五个重要特性:输入、输出、有穷性、拟定性、可行性。程序（Ｐｒogrａｍ)是对一个算法使用某种程序设计语言的具体实现，原则上，算法可以用任何一种程序设计语言来实现。什么是算法的计算复杂性？算法分析指的是对算法所需要的两种计算机资源——时间和空间(时间复杂性和空间复杂性进行估算，所需要的资源越多,该算法的复杂性就越高。表达计算复杂性的O你掌握了?若存在两个正的常数c和n0,对于任意n≥n0,都有T(ｎ)≤c×ｆ(n)，则称Ｔ(ｎ）=Ｏ(ｆ（n））(或称算法在O（f(n)）中)。我们重要介绍了哪几种算法设计方法?分治法:将一个难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破,分而治之。减治法：减治法在将原问题分解为若干个子问题后,运用了规模为n的原问题的解与较小规模（通常是ｎ／2)的子问题的解之间的关系,这种关系通常表现为:(1)原问题的解只存在于其中一个较小规模的子问题中;(2)原问题的解与其中一个较小规模的解之间存在某种相应关系。由于原问题的解与较小规模的子问题的解之间存在这种关系，所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。动态规划法、贪心算法、回溯算法、概率RAM程序分治法-－----合并排序设算法4.３对ｎ个元素排序的时间复杂性为T(n)，则该二路归并排序算法存在如下递推式:二路归并排序的时间代价是O(nｌog2ｎ)。所需空间只要O(m+ｎ＋min(m,n）)的空间就够了(假设两个合并串的长度分别为ｍ和n)。分治法--－---快速排序在最佳情况下在具有n个记录的序列中,一次划分需要对整个待划分序列扫描一遍,则所需时间为O（n)。时间复杂度为O(nlｏg２n）。在最坏情况下必须通过n-1次递归调用才干把所有记录定位,并且第i趟划分需要通过n-i次关键码的比较才干找到第i个记录的基准位置,因此，总的比较次数为：时间复杂度为O(n2)分治法-----－最大子段递推式:算法时间复杂度:O(nｌｏg2n)分治法--－－-－棋盘覆盖问题Ｔ(ｋ)满足如下递推式:分治法------循环赛日安排问题基本语句的执行次数是:算法的其时间复杂性为Ｏ（４k）。顺序记录问题:算法1找出n个元素中的第ｋ个最小元素输入:从一个有线性序的集合中抽出的ｎ个元素的序列Ｓ及一个整数k，1≤k≤ｎ。输出:S中的第k个最小元素算法2算法2的盼望时间是O(n)。最坏情况O（n2）减治--－--插入排序(手工题）堆的概念:ｎ个元素的序列{K1,Ｋ2,…．．Kn｝,当且仅当满足动态规划求解TSP问题注：用动态规划解决TSP问题，算法的时间复杂性为Ｏ（ｎ22n)。和蛮力法相比，动态规划法求解TＳＰ问题，把本来的时间复杂性是Ｏ(n!)的排列问题，转化为组合问题,从而减少了算法的时间复杂性,但它仍需要指数时间。但遗憾的是这一动态规划算法需要Ｏ（n２n)的空间。当n较大时,空间难以满足。多段图的最短途径算法：1.Foｒ(i=1;i<=n；i+＋）COST[i]=0;初始化：数组ｃｏsｔ[ｎ]初始化为最大值，数组pａtｈ[n］初始化为-1；2．foｒ(i＝n-２;i＞=0；i--)2.１对顶点i的每一个邻接点ｊ，根据cｏｓt[i］=ｍｉn{cij＋coｓｔ[ｊ］｝（i≤ｊ≤n且顶点j是顶点i的邻接点)计算ｃost[i]；2．２根据ｐath[i］=使cｉj＋coｓt[ｊ]最小的ｊ计算path[i];3.输出最短途径长度ｃost[0];４.输出最短途径通过的顶点：4.1i=04.2循环直到ｐａth[i]=n－14.2.1输出ｐaｔｈ[i];4．2.2i＝paｔｈ［i]；最优二叉查找树算法:最优二叉查找树是以这n个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树,即最小,i=1n回溯法－-－-解空间树的动态搜索过程注:搜索过程中,采用两种策略避免无效搜索:用约束条件剪去得不到可行解的子树;用目的函数剪去得不到最优解的子树。例一:对于n=3的0/1背包问题，三个物品的重量为{２0，15,10｝，价值为{20,30,25｝，背包容量为25,从图８．2所示的解空间树的根结点开始搜索，搜索过程如下:(注:树枝左侧为1,右侧为0,1代表装包，０代表不装包,从上到下每一层代表一个物体)例二:对于n＝4的ＴＳP问题,解空间树如下:代价矩阵Ｃ如下：目的函数初始化为∞；从结点１选择第1棵子树到结点2，表达在图中从顶点1出发；从结点2选择第1棵子树到达结点３，表达在图中从顶点1到顶点２，依代价矩阵可知途径长度为3；从结点3选择第１棵子树到达结点4,表达在图中从顶点2到顶点3，依代价矩阵可知途径长度为3+2=5;从结点４选择唯一的一棵子树到结点５，表达在图中从顶点３到顶点4,途径长度为5+2=7,结点5是叶子结点,找到了一个可行解,途径为1→2→3→4→1,途径长度为７+3=10,目的函数值10成为新的下界,也就是目前的最优解;从结点５回溯到结点４,再回溯到结点3，选择结点3的第2棵子树到结点6,表达在图中从顶点2到顶点4,途径长度为3+8＝１1，超过目的函数值1