JAVA实现算法设计策略_【数据结构与算法+研一课程ppt】

本文主要是介绍JAVA实现算法设计策略_【数据结构与算法+研一课程ppt】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.Fibonacci数列：o(n)

 public static void Fibonacci(int n ){int a = 0;int b = 1;System.out.println(a);System.out.println(b);for (int x = 0;x < n-1 ;x++){int c = a+b;a = b;b = c;System.out.println(c);}}

2.矩阵乘积：o(n[3])

 public static int[][] Matrixmultiplication(int[][] a,int[][] b){int hang = a.length;int lie = b[0].length;int num = a[0].length;int[][] c = new int[hang][lie];for (int x = 0;x<hang;x++){for (int y = 0;y<lie;y++){int count = 0;for (int k = 0;k<num;k++){count = count + a[x][k]*b[k][y];}c[x][y] = count;}}return c;}

此后感觉讲得比较乱，换用研一课程的算法ppt重新开始看；

1.

P	多项式时间内可以解决
NPC	无法在多项式时间内解决
NP	多项式时间内可验证

2.复杂度

o(c) < o (logn) < o(n) < o(nlogn) < o(n[r]) < o(r[n]) < o(n!)

3.贪心算法：局部最优不一定导致全局最优或正确；证明通常采用反证法；

时间安排算法(不带权重）：贪心算法，按最早结束时间进行排序，选择不重复的；nlogn

整数相加	o(n)
整数相乘：xy=2[n] * x1y1+2[n/2](x0y1+x1y0)+x0y0  = 2[n] * x1y1 + 2[n/2]((x1+x0)(y1+y0)-x1y1-x0y0) + x0y0	o(n[1.5])

矩阵乘法：T(n) = 7 T (n/2) +dn[2]

o(2.8)

5.动态规划：将问题分解为更小的问题，更小的问题之间通常互相联系，通过小问题的解决达到大问题的解决；

带权重的时间安排算法：opt(j) = {vj+opt(P(j)) , opt(j-1)} max；需要暂存中间结果；

o(nlogn)

背包问题：opt(i,w) =  { 0 : i = 0; opt(i-1,w) : wi > w ; max{opt(i-1,w),opt(i-1,w-wi) + vi} NPC问题

o(nw)

6.线性规约 

当问题x可以依靠多项式时间的简单操作及多项式次数的Y的解决方案而解决，则x线性规约到y；

y若是多项式时间可解，则x也在多项式时间内可解；

这篇关于JAVA实现算法设计策略_【数据结构与算法+研一课程ppt】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---