算法 复习提纲

《算法 复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。23空间复杂度O(1)，O(logn)，O(n)，O(nlogn)，O(n)，O(n)的升序排列给出一小段简单的程序，会分析时间复杂度和空间复杂度分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的问题，以便各个击破，分而治之，规模较小的问题再分割成规模更小的

2、子问题，一直到子问题的规模足够小，可以直接解决为止。接着从最小规模的子问题求解开始，不断地进行合并子问题的解，得到较大子问题的解，一直到原问题的解为止。直接或间接地调用自身的算法称为递归算法。分治法的算法一般写成容易理解递归算法。当然也可以改成非递归的算法，但理解上不直观。递归小结:优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：1.该问题的规模缩小到一

3、定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题，即该问题具有子结构性质3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balan

4、cing)子问题的思想，它几乎总是比子问题规模不等的做法要好。二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。二分搜索算法：publicstaticintbinarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;

5、if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;//未找到x}算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。合并排序：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空

6、间：O(n)快速排序:最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)Strassen矩阵乘法原理动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质1．利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。2.递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。自底向上算法虽然子问题有重叠，但对每一个子问题只解一次。从规模最小的子问题开始求解，逐层地向上求出规模较

7、大的子问题，直到求出原问题的解。如果子问题大量重复计算，时间花费较多，往往达到指数阶。但是不同的子问题个数随问题的大小呈多项式增长。因此用自底向上的方式计算，只需要多项式时间，从而获得较高的解题效率。备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，对每一个子问题只解一次，而后将其解保存在一个表格中（称为备忘录），当再次需要解此子问题时，只是简单地用常数时间查看一下结果。备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，从而避免了相同子问题的重复求解。动态规划基本步骤:1.找出最优解的性质，并刻划其结构特征。2.递归地定义最优值。3.以自

8、底向上的方式计算出最优值。4.根据计算最优值时得到的信息，构造最优解。动态规划基