算法简述 (加强版)

《算法简述 (加强版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法简述：第一章：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.

2、6理由参照以上说明即可搞定第二章：分治思想第一部分：课堂笔记一：二：递归树：计算时间……………………最后一层11111111完全二叉树，推得层数为logn，那么时间复杂度为不对称递归树解法与上述一致，只是对不对称处理注一点即可分治法，将一个规模为n的问题分为k个的子问题，这些子问题相互独立且与原问题相同递归的求解的这些子问题；不妨设k个子问题规模为n/m,分解发值为n0=1，设k个子问题解合并为原问题的解需f(n)个单位时间递归式：=>推导式1：，简化一下注简化式只在求时间复杂度使用，其他状况勿用！以分治发派生出：大

3、整数的乘法、棋盘覆盖、矩阵乘法、合并排序、快速排序、线性时间排序，这些虽然不会原题出现，但其中两个的思想方法会在考试中出现，分析分析，他们的思想递归式、时间复杂度即可最好会用！(以上面递归式和推导式1很容易搞定)参考习题2.3，2.9习题2.9第三章：解题形式，四步一、算法策略（以什么思想解题，是动态规划还是贪心算法或是分治算法）；二、算法思想（按第一步往下分析，按套路走下去。列如，第一步说是动态规划，那么把题目带进动态规划套路，段分成多少子问题，假定某个方向最优，自低向上分析等等相似的贪心算法也如此，最后最好加一点

4、递归式推导式什么等等，）；三、算法实现；（程序，比一般程序简单多，不要求写出得合乎语法结构，形式化东西，汉语加程序语言叙述）四、算法时间复杂度分析（即大O()多少什么）。3.1矩阵相乘3．3最长公共子序列3.4最大子段和3.7图像压缩3.100-1背包问题（课堂有例子，找出来！做做！！！）课后参考习题算法分析题第三章，算法实现题：习题.3.2算法实现题3.3.注以上解法勿用：简洁解法如下：注意时间复杂度算法实现题3.5算法实现题3.6分析：给出的算法是自低向上，那么递归式必定为自上而下，其实就是上三角问题，贪心确实很

5、好用，每次选取的都是最大的，整个不就最大。《但这题要动态解，》换个角度，这也是最优子结构问题，采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n,则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。即在上三角每行选个数求，row代表行，col代表列；以一个二维数组来trangle[][]保存当前最大和，递归式如下：算法描述如下：（原答案有误，已改！）算法实现：（c版）#include"stdio.h"#

6、include"math.h"main(){FILE*fp1,*fp2;inta[105][105];inti,j;intn;charc[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]

7、[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",a[1][1]);/*循环完毕后，三角形最顶端的点所存的值即为最大的和，输出这个值*/for(i=1;i<=n;i++)fprintf(fp2,"%c",c[i]);fclose(

8、fp2);}时间复杂度第四章：贪心算法考试分值20%左右第四题问答题出现，加一道选择题或一题填空考试内容：活动安排、哈弗曼编码、单源最短路径，最小生成树、多级调度虽然列了多条，分开来看：多级调度调度必考，但是只是一道填空或是选择，解题方法——书P121哈弗曼编码、单源最短路径，最小生成树此三者，数据结构，翻开看看，加一点算法知识（即上课老师说的