算法简述 (加强版).docVIP

算法简述： 第一章： 1．考试分值30%，题型选择、填空占90%，其他以附属形式出现 2．了解四个渐近阶（ 、、、）含义，运算，简单判断 简单描述如下，设有正函数f(n)和g(n)， I、存在正常数、，使得当n时，有f(n) *g(n) 记为f(n)= (g(n))，函数的 一般上界 II、存在正常数、，使得当n时，有f(n) *g(n) 记为f(n)= (g(n))，函数的一般下界 III、同时满足上两条，记为f(n)= (g(n))， IV、至于，即，记为f()=(g()); 参考习题1.1， 1.3, 1.6(重点，答案不全，理由自己补充)。 习题1.6 理由参照以上说明即可搞定 第二章：分治思想 第一部分： 课堂笔记 一： 二： 递归树： 计算时间 …………………… 最后一层1 1 1 1 1 1 1 1 完全二叉树，推得层数为logn，那么时间复杂度为 不对称递归树解法与上述一致，只是对不对称处理注一点即可 分治法，将一个规模为n的问题分为k个的子问题，这些子问题相互独立且与原问题相同递归的求解的这些子问题；不妨设k个子问题规模为n/m,分解发值为n0=1，设k个子问题解合并为原问题的解需f(n)个单位时间 递归式：= 推导式1：，简化一下 注简化式只在求时间复杂度使用，其他状况勿用！ 以分治发派生出：大整数的乘法、棋盘覆盖、矩阵乘法、合并排序、快速排序、线性时间排序，这些虽然不会原题出现，但其中两个的思想方法会在考试中出现，分析分析，他们的思想递归式、时间复杂度即可 最好会用！(以上面递归式和推导式1很容易搞定) 参考习题2.3 ，2.9 习题2.9 第三章： 解题形式，四步 算法策略（以什么思想解题，是动态规划还是贪心算法或是分治算法）； 算法思想（按第一步往下分析，按套路走下去。列如，第一步说是动态规划，那么把题目带进动态规划套路，段分成多少子问题，假定某个方向最优，自低向上分析等等相似的贪心算法也如此，最后最好加一点递归式推导式什么等等，）； 算法实现；（程序，比一般程序简单多，不要求写出得合乎语法结构，形式化东西，汉语加程序语言叙述） 算法时间复杂度分析（即大O()多少什么）。 3.1矩阵相乘 3．3最长公共子序列 3.4最大子段和 3.7图像压缩 3.10 0-1背包问题（课堂有例子，找出来！做做！！！） 课后参考习题 算法分析题 第三章，算法实现题： 习题.3.2 算法实现题3.3. 注以上解法勿用： 简洁解法如下： 注意时间复杂度 算法实现题3.5 算法实现题3.6 分析：给出的算法是自低向上，那么递归式必定为自上而下，其实就是上三角问题，贪心确实很好用，每次选取的都是最大的，整个不就最大。《但这题要动态解，》换个角度，这也是最优子结构问题， 采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。每行选个数求，row代表行，col代表列；以一个二维数组来trangle[][]保存当前最大和， 递归式如下： 算法描述如下：（原答案有误，已改！） 算法实现：（c版） #include stdio.h#include math.h main(){FILE *fp1,*fp2;int a[105][105];int i,j;int n;char c[105];fp1=fopen(numr.txt,rt);fscanf(fp1,%d,n);for(i=1;i=n;i++){??? for(j=1;j=i;j++)????? fscanf(fp1,%d,a[i][j]);}fclose(fp1);for(i=n-1;i=1;i--){ for(j=1;j=i;j++) { if(a[i+1][j]=a[i+1][j+1]){ a[i][j]=a[i][j]+a[i+1][j];c[i]=L;}else{a[i][j]=a[i][j]+a[i+1][j+1];c[i]=R;}/*倒推。判断从（i，j）这个点开始往下走的最大的和，并存在这个点上。*/}}fp2=fopen(numw.txt,wt);fprintf(fp2,%d\n,a[1][1]);/*循环完毕后，三角形最顶端的点所存的值即为最大的和，输出这个值*/for(i=1;i=n;i++)fprintf(fp2,%c,c[i]);fclose(fp2);} 时间复杂度 第四章： 贪心算法 考试分值20%左右 第四题问答题出现，加一道选择题或一题填空 考试内容：活