发布时间 : 星期一 文章江西理工大学算法设计与分析复习资料更新完毕开始阅读
1.、算法是解决问题的方法和过程。具有下列性质： 输入：有零个或者多个输入； 输出：至少有一个输出；
确定性：组成算法的每条指令都是清晰的，无歧义的； 有限性：算法中的每条指令的执行次数有限，运行每条指令的时间有限。 2、二分搜索：
Public static int binarySearch(int []a,int x,int n) {
Int left=0,int right=n-1; While (left<=right) {int middle =(left+right)/2;
If (x==a[middle]) return middle; If (x>a[middle]) left=middle +1; Else right =middle-1;} Return -1; }
3、动态规划的思想就是把求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到元问题的解。 步骤：
（1）找出最优解的性质，并刻画其结构特征 （2）递归的定义最优值；
（3）以自低向上的方式计算出最优值；
（4）根据计算最优值时得到的信息，构造最优解； 4、矩阵连乘：
Public static void matrixChaiin(int []p,int [][]m,int [][]s) {
Int n=p.length-1;
For (int i=1;i<=n;i++) m[i][i]=0; For (int r=2;r<=n;r++) For (int i=1;i<=n-r+1;i++) {int j=i+r-1;
M[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; S[i][j]=i;
For (int k=i+1;k {int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; If (t Public static void traceback(int [][]s,int i,int j) {if (i==j) return; Traceback(s,i,s[i][j]); Traceback(s,s[i][j]+1,j); System.out.println(\A\ A\} 5、0-1背包问题： Public static void knapsack(int []v,int []w,int c,int [][]m) { Int n=v.length-1; Int jMax=Math.min(w[n]-1,c); For (int j=0;j<=jMax;j++) m[n][j]=0; For(int j=w[n];j<=c;j++) m[n][j]=v[n]; For (int i=n-1;i>1;i--) {jMax=Math.min(w[i]-1,c); For(int j=0;j<=jMax;j++) M[i][j]=m[i+1][j]; For (int j=w[i];j<=c;j++) M[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]+v[i]);} M[1][c]=m[2][c]; If (c>=w[1]) M[i1[c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]); } Public static void traceback(int [][]m,int[]w,int c,int []x) { Int n=w.length-1; For (int i=1;i If (m[i][c]==m[i+1][c]) x[i]=0; Else {x[i]=1; c-=w[i];} X[n]=(m[n][c]>0)? 1:0; } 6、贪心算法的基本思想：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。贪心算法并不考虑整体的最优，他做出的只是当前最优的选择。 基本要素：①贪心选择性质 ②最优子结构性质。 7、回溯法的基本思想：确定解空间的组织结构后，回溯法从根节点开始，以深度优先方式搜索整个解空间。这个开始节点为货节点，也称为扩展节点。从开始节点搜索至新节点处，当搜索到某个节点处不能再向纵深方向搜索，则回溯至上一个节点，直到找到需要的解为止。 求解步骤： ①针对所给问题，定义问题的解空间； ②确定易于搜索的解空间结构； ③以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 回溯法与分支界限法的比较： 相同点：两者在问题进行求解前，都需要完成解空间的定义和组织 都是通过在解空间树上搜索来寻找问题的解 不同点：回溯法在解空间树（子集树、排列树）上的搜索方式是深度优先；分支限界算法在解空间树（子集树、排列树）上的搜索方式是广度优先。 8、证明：O(f)+ O(g)= O(f+g) 令 F[N]=O[f],则存在自然数N1,C1,使得对任意的自然 数N>=N1，有：F（N）<=C1f[N]; 令：G[N]=O[g],则存在自然数N2,C2,使得对任意的自然 数N>=N2，有：G（N）<=C2g[N]; 令C3=max{C1,C2},N3=max{N1,N2},则对所有的 N>=N3,有 F[N]<=C1f(N)<=C3f(N); G[N]<=C2f(N)<=C3g(N); 故有： O(f)+O(g)=F(N)+G(N)<=C3f(N)+C3g(N)=C3(f(N)+g(N))=O(f+g); 因此有：O(f)+ O(g)= O(f+g) 9、证明：n!=O(nn) 证明： 10、证明：如果一个算法在平均情况下的计算时间复杂度为θ（f（n）），则该算法在最坏的情况下所需的计算时间为Ω（f（n））。 证 明 ： 10、最优装载问题： Public class Loading { Static int n; Static int []w; Static int c; Static int cw; Static int bestw; Public static int maxLoading (int [] ww, int cc) { N=ww.length-1; W=ww; C=cc; Cw=0; bestw=0; Backtrack(1); Returm bestw; } Private static void backteack (int i) { If (i>n) { if (sw>bestw) bestw=cw; Return; } If (cw+w[i]<=c) {cw+=w[i]; Backtrack(i+1); Cw-=w[i];} Backtrack(i+1) } }