(1)班算法设计期末复习(补)VIP专享VIP免费

第一章算法引入1.算法的八大基本步骤：问题分析、建立数学模型、算法的设计与选择、算法分析、算法表示、实现算法、程序调试、结果整理文档。2.算法的三大要素：操作、控制结构、数据结构。3.算法的四大基本特征：输入、输出、确定性、有限性。*补充（输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。）4.对算法的评价有两个大的方面：人对算法的维护的方便性、算法在实现运行时占有的机器资源的多少即算法的运行的时间和空间效率。5.算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需要的资源越多该算法的复杂性越高，反之所需要的资源越少该算法的复杂性越低。6.算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性。需要的空间的量称为空间复杂性。7.算法复杂性包括时间复杂性和空间复杂性。8.一个算法中所有语句的频度之和构成了该算法的运行时间。9.以上时间复杂度级别是由低到高排列的,其随规模n的增长率，由图1图1T(n)与规模n的函数关系10.对较复杂的算法，计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。11.而度量一个程序的执行时间通常有两种方法。一、事后统计的方法二、事前分析估算的方法第二章递归与分治策略1.分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，以便各个击破，分而治之。2.分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。3.（简答题）分治法的适用条件（特征）：①该问题的规模缩小到一定的程度就可以容易地解决；②该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质③利用该问题分解出的子问题的解可以合并为该问题的解；④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4.△二分搜索技术P23：（二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O（logn）时间完成搜索任务。（即最坏情况下计算时间复杂度为O（logn））二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x，算法终止。如果xa[n/2]，则只要在数组a的右半部继续搜索x。二分搜索算法具体算法描述：publicstaticintbinarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x，找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;While(left<=right){{intmiddleO(logn)=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle)left=middle+1；elseright=middle-1;}return-1;//未找到x}5.合并排序p29（只要记住算法思路）：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。最坏时间复杂度：O(nlogn)，平均时间复杂度：O(nlogn)。6.快速排序p31（只要记住算法思路）：在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)7.排序的算法复杂性为O(logn)，合并排序与快速排序中，合并排序更稳定。第三章动态规划1.（简答题）动态规划算法四大基本步骤（①②③必须实现，④只有求出最优值才执行）①找出最优解的性质，并刻画其结构特征；②递归地定义最优值；③以自底向上的方式计算出最优值；④根据计算最优值时得到的信息，构造最优解。2.动态规划算法的基本要素：最优子结构性质和子问题重叠性质。3.最长公共子序列P58P60（理解补充）若给定序列X={,,…,}，则另一序列Z={,,…,}，X的子序列是...