认识达内从这里开始

掌握不同的算法能够让大多数Java编程开发程序员满足不同的软件编程开发需求，而本文我们就通过案例分析来简单了解一下，Java程序员需要掌握哪些编程算法。

一、贪婪算法(Greedy)

Greedy方法多用于需要优化且局部优解导致全局优解的问题。

也就是说，当使用Greedy时，每一步的优解都会导致整体优解。然而，在大多数情况下，我们在一个步骤中做出的决定会影响下一步的决定列表。在这种情况下，必须用数学方法证明算法。Greedy也会在一些数学问题上产生很好的解决方案，但不是全部(可能无法保证佳解决方案)!

贪心算法通常有五个组成部分：

候选集——从中创建解决方案;

选择函数——选择佳候选人;

可行性函数——可以确定候选人是否能够为解决方案做出贡献;

一个目标函数——将候选人分配给(部分)解决方案;

一个解决方案函数——从部分解决方案构建解决方案。

分数背包问题

给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的大总价值(允许取件物品：一件物品的价值与其重量成正比)。

贪心方法的基本思想是根据它们的价值/重量比对所有项目进行排序。然后，我们可以添加尽可能多的整个项目。当我们发现一件比背包中剩余重量(w1)重(w2)的物品时，我们将对其进行分割：仅取出w2-w1以大化我们的利润。保证这个贪心的解决方案是正确的。

二、动态规划(DynamicProgramming)

动态规划(DP)是一种类似于分而治之的方法。它还将问题分解为类似的子问题，但它们实际上是重叠和相互依赖的——它们不是独立解决的。

每个子问题的结果都可以在以后随时使用，它是使用记忆(预先计算)构建的。DP主要用于(时间和空间)优化，它基于寻找循环。

三、长公共子序列(LongestCommonSubsequence)

给定两个序列，找出它们中存在的长子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。

这是动态规划的另一个应用。LCS算法使用DP来解决上述问题。

实际的子问题是要分别从序列A中的索引i开始，分别从序列B中的索引j中找到长公共子序列。

接下来，我们将构建DP结构lcs[][](矩阵)，其中lcs[i][j]是从A中的索引i开始，分别是B中的索引j的公共子序列的大长度。我们将以自顶向下的方式构建它。显然，解决方案存储在lcs[n][m]中，其中n是A的长度，m是B的长度。

递推关系非常简单直观。为简单起见，我们将考虑两个序列都是1索引的。先，我们将初始化lcs[i][0],1<=i<=n和lcs[0][j],1<=j<=m,0,作为基本情况(没有从0开始的子序列)。然后，我们将考虑两种主要情况：如果A[i]等于B[j]，则lcs[i][j]=lcs[i-1][j-1]+1(比之前的LCS多一个相同的字符)。否则，它将是lcs[i-1][j](如果不考虑A[i])和lcs[i][j-1](如果不考虑B[j])之间的大值)。

时间复杂度：O(n*m)

附加空间：O(n*m)

四、长递增子序列(LongestIncreasingSubsequence)

给定一个包含n个元素的序列A，找到长子序列的长度，使其所有元素按递增顺序排序。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。

LIS是另一个可以使用动态规划解决的问题。

使用数组l[]作为DP结构来寻找递增子序列的大长度，其中l[i]是包含A[i]的递增子序列的大长度，其元素来自[A[i]],...,A[n]]子序列。l[i]为1，如果A[i]之后的所有元素比它小。否则，在A[i]之后大于它的所有元素之间的大值为1+。显然，l[n]=1，其中n是A的长度。实现是自底向上的(从末尾开始)。

在搜索当前元素之后的所有元素之间的大值时出现了一个优化问题。我们能做的好的事情是二分搜索大元素。

为了找到现在已知的大长度的子序列，我们只需要使用一个额外的数组ind[]，它存储每个大值的索引。

时间复杂度：O(n*logn)

附加空间：O(n)

五、凸包算法(ConvexHull)

给定同一平面中的一组n个点，找到包含所有给定点(位于多边形内部或其边上)的小面积凸多边形。这种多边形称为凸包。凸包问题是一个的几何，在现实生活中有很多应用。例如，碰撞避免：如果汽车的凸包避免碰撞，那么汽车也能避免碰撞。路径的计算是使用汽车的凸表示完成的。形状分析也是在凸包的帮助下完成的。这样，图像处理很容易通过匹配模型的凸缺陷树来完成。

有一些算法用于寻找凸包，如Jarvis算法、Graham扫描等。今天我们将讨论Graham扫描和一些有用的优化。

格雷厄姆扫描按极角对点进行排序——由某个点和其他选定点确定的线的斜率。然后用一个栈来存储当前时刻的凸包。当一个点x被压入堆栈时，其他点会被弹出堆栈，直到x与后两个点所确定的线形成小于180°的角度。后，引入堆栈的后一个点关闭多边形。由于排序，这种方法的时间复杂度为O(n*logn)。但是，这种方法在计算斜率时会产生精度误差。

一种改进的解决方案具有相同的时间复杂度，但误差较小，按坐标(x，然后是y)对点进行排序。然后我们考虑由左边和右边的点形成的线，并将问题分为两个子问题。后，我们在这条线的每一边找到了凸包。所有给定点的凸包是两个包的重聚。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。