算法
算法(Algorithm)是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
在 Java 中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。
算法的五个特征
一个算法应该具有以下五个重要的特征：
有穷性(Finiteness)：算法的有穷性是指算法必须能在执行有限个步骤之后终止。确定性(Definiteness)：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径。可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成(也称之为有效性)。有输入(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。有输出(Output)：个算法有一个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。
算法的设计原则
一个算法应该具有以下四个重要的设计原则：
- 正确性：算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需要、能够得到问题的正确答案。
算法的“正确”通常在用法上有很大的差别，大体分为以下4个层次：
① 算法程序没有语法错误；
② 算法程序能够根据正确的输入的值得到满足要求的输出结果；
③ 算法程序能够根据错误的输出的值满足规格说明的输出结果；
④ 算法程序对于精心设计、极其刁难的测试数据都能满足要求的输出结果。
对于这4层含义，层次①要求最低，因为仅仅没有语法错误实在谈不上是好的算法。而层次④是最困难的，人们几乎不可能逐一验证所有的输入都得到正确的结果。
因此，算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，人们把层次③作为一个算法是否正确的标准。 - 可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。
- 健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
- 高效与低存储：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。
在满足以上几点以后，还可以考虑对算法进程进一步优化，尽量满足时间效率高和空间存储量低的需求。
算法的设计步骤
算法设计的一般过程可以归纳为以下几个步骤：
- 建立数学模型；
- 通过对问题进行详细的分析，抽象出相应的数学模型；
- 确定数据结构与算法；
- 确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；
- 选用语言；
- 选用某种语言将算法转化成程序；
- 调试并运行；
- 调试并运行这些程序。
算法的基本思想
穷举算法思想
穷举算法思想就是从所有的可能结果中一个一个的试验，知道试出正确的结果。具体的操作步骤如下：
- 对每一种可能的结果，计算其结果；
- 判断结果是否符合题目要求，如果符合则该结果正确，如果不符合则继续进行第1步骤。
穷举算法思想的经典例子为鸡兔同笼为题（又称龟鹤同笼问题）。
递推算法思想
递推算法算法就是根据已知条件，利用特定关系推导出中间推论，直到得到结果的算法。其执行过程如下：
- 根据已知结果和关系，求解中间结果。
- 判断是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确答案。
递推算法思想最经典的例子是斐波那契数列 : 1,1,2,3,5,8,13……
递归算法思想
递归算法思想是把大问题转换成同类问题的子问题，然后递归调用函数表示问题的解。在使用递归的时候一定要注意调回递归函数的终止条件。
递归算法的分类：
- 直接递归：在函数中调用自身。
- 间接递归：在函数中调用另外一个函数，然后在另外一个函数中再调用该函数(用得不多)。
递归算法比较经典的例子是求阶乘。
分治算法思想
分治算法思想就是把一个大问题分解成若干个规模较小的子问题，且这些子问题的都是相互独立的、与原问题性质一致。逐个求出这些子问题的解就能够得到原问题的解了。其执行过程如下：
- 对于一个规模为 N 的问题，若该问题可以容易地解决（比如说规模 N 较小），则直接解决，否则执行下面的步骤。
- 将该问题分解为 M 个规模较小的子问题，这些子问题互相独立，并且与原问题形式相同。
- 递归的解子问题。
- 然后，将各子问题的解合并到原问题的解。
分治算法思想有一个比较经典的例子就是查找假币问题。
概率算法思想
概率算法主要包括四种算法：
- 数值概率算法：数值问题的求解，最优化问题的近似解。
- 蒙特卡罗算法：判定问题的准确解，不一定正确。
- 拉斯维加斯算法：不一定会得到解，但得到的解一定是正确解。
- 舍伍德算法：总能求得一个解，且一定是正确解。
