资源描述：
《算法设计期末复习.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章算法引入1、算法的八大基本步骤：问题分析、数学模型建立、算法的设计与选择、算法分析、算法表示、算法实现、程序调试、结果整理文档编制（算法设计是解决问题的核心）2、算法的三大要素：操作、控制结构、数据结构。3、算法的四大基本特征：输入、输出、确定性、有限性。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。4、对算法的评价有两个大的方面：人对算法的维护的方便性、算法在
2、实现运行时占有的机器资源的多少即算法的运行的时间和空间效率。5、和算法执行时间相关的因素：（1）问题中数据存储的数据结构；（2）算法采用的数学模型；（3）算法设计的策略；（4）问题的规模；（5）实现算法的程序设计语言；（6）编译算法产生的机器代码的质量；（7）计算机执行指令的速度6、算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需要的资源越多该算法的复杂性越高，反之所需要的资源越少该算法的复杂性越低。（算法复杂性包括时间复杂性和空间复杂性）7、一个算法中所有语句的频度之和构成了该算
3、法的运行时间。8、以上时间复杂度级别是由低到高排列的,其随规模n的增长率，图1T(n)与规模n的函数关系第二章递归与分治策略1、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2、（简答题）分治法的适用条件（特征）：①该问题的规模缩小到一定的程度就可以容易地解决；②该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；③利用该问题分解出的子问题的解可以合并为该问题的解；④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公
4、共的子问题。3、二分搜索技术（P23）△二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O（logn）时间完成搜索任务二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x，算法终止。如果xa[n/2]，则只要在数组a的右半部继续搜索x。二分搜索算法具体算法描述（代码填空）publicstaticintbinarySearch(int[]a,intx,int
5、n){//在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}3、合并排序（p29）（选择题计算复杂度，只要记住算法思
6、路）将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。最坏时间复杂度：O(nlogn)，平均时间复杂度：O(nlogn)。4、快速排序（p31）（只要记住算法思路）在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)总结：排序的算法复杂性为O(
7、logn)，合并排序与快速排序中，合并排序更稳定。第二章动态规划1、（简答题）动态规划算法四大基本步骤（①②③必须实现，④只有求出最优值才执行）①找出最优解的性质，并刻画其结构特征；②递归地定义最优值；③以自底向上的方式计算出最优值；④根据计算最优值时得到的信息，构造最优解。2、动态规划算法的基本要素：最优子结构性质和子问题重叠性质（2大要素）3、最长公共子序列（P58、P60）（理解补充）若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格
8、递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的
