​

转载本文需注明出处：微信公众号EAWorld，违者必究。

引言：

Google搜索的结果，新浪微博向你展示的话题，淘票票向你推荐的电影，都说明了算法无处不在。而编程从本质上来说就是算法加数据结构 ，算法是编程思想的核心部分，对于一名基础软件工程师而言，常见的一些算法也是必须重点掌握的内容。而常见的算法以及其应用场景有哪些呢？

目录：

1. 算法概述

2. 常用算法的理论分析

3. 常用算法的实际应用

1. 算法概述

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

1.1 算法特征

有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止；确切性：算法的每一步骤必须有确切的定义；输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

1.2 算法衡量标准

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。而算法的整体考量包含以下几个内容：

时间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做:T(n)=Ο(f(n))。因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。空间复杂度：算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。正确性：算法的正确性是评价一个算法优劣的最重要的标准。可读性：算法的可读性是指一个算法可供人们阅读的容易程度。健壮性：健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。2. 常用算法的理论分析

算法包含的内容有很多，对于基础软件工程师而言，虽然不需要面面俱到，但对于常用的算法还是要学习掌握。常见算法包括：分治法、递归法、贪心算法和回朔法。

2.1 分治法：

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

能用分治法解决的问题，一般符合以下特征：

该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

如果确定一个问题可以用分治法进行求解，可以按照分治法的求解步骤处理。求解步骤如下：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并：将各个子问题的解合并为原问题的解。

2.2 递归法

程序调用自身的编程技巧称为递归（recursion）。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。而能够使用递归处理的问题一般具备以下特征：

可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。存在一种简单情境，可以使递归在简单情境下退出。

如果确定一个问题可以用递归法进行求解，可以按照递归法的求解步骤处理。求解步骤如下：

确定边界条件确定不满足边界条件时的递归前进段确定满足条件时递归返回段

2.3 回朔法

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。

探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。递归的能力在于用有限的语句来定义对象的无限集合。

如果确定一个问题可以用回溯法进行求解，可以按照回溯法的求解步骤处理。求解步骤如下：

针对所给问题，定义问题的解空间。确定易于搜索得解空间结构。以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

2.4 贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

能用贪心算法处理的问题，通常具有以下特点：

可行的：即它必须满足问题的约束。局部最优：他是当前步骤中所有可行选择中最佳的局部选择。不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

一旦问题确定可以用贪心算法处理，我们可以按照贪心算法常用的步骤，进行解答。步骤如下：

建立数学模型来描述问题；把求解的问题分成若干个子问题；对每一子问题求解，得到子问题的局部最优解；把子问题的解局部最优解合成原来解问题的一个解。3.常用算法的实际应用

每种算法都有很多应用场景，但算法的思想却是一致，因此我们选取算法众多应用场景中的一个，来分析该算法的使用形式。基于上面讲解的四种算法，我们分别选择一个实例作为分析，依次如下：

分治法：二分查找问题递归法：文件夹删除问题贪心算法：货币找零问题回朔法：旅行售货员问题

而针对这些问题，我们通过分析问题特征，根据算法特征提取算法执行时要素，一步步完成问题的解答。

3.1 分治法实例

问题：

有一个包含10000个数据的有序数组，给定一个数n， 确定该数在数组中的位置。

问题分析：

想要查找数在数组中的位置，最容易想到的是遍历数组，在数组长度小的时候，可能很容易实现，但数组很大时，再通过遍历，会严重影响算法的效率。因此需要考虑其他方式。

既然数据有序，那么可以先取出，数组中中间数据，判断所找数据是否符合要求，若不符合，就判断是大于中间值，还是小于中间值。确定好范围，此时若是再次遍历，可以节省一半的时间开销。基于这种思想，我们可以再次取中间值，不用遍历，可以大大提高算法效率。

提取算法要素：

1. 先确定中间位置

根据数组长度，确定中间位置，找到中间位置数据

2. 根据判断结果，选定查找范围

将待查找的数据与数组中间位置数据值相比较。若相等，则查找成功并返回该位置，否则须确定新的查找区间，继续二分查找。

关键代码：

上述例子只是分治法众多经典应用场景之一，而分治法还有其他很多经典应用场景，大家有兴趣可以自己去学习一下。分治法其他经典实例：

汉诺塔大整数乘法Strassen矩阵乘法棋盘覆盖合并排序快速排序线性时间选择最接近点对问题循环赛日程表　

3.2 递归法实例

问题：

删除指定路径文件夹。

问题分析：

文件或者空文件夹可以删除，但是若文件夹中包含有子文件或文件夹，则无法直接删除。

因此需要把文件夹里面的文件依次全部删除，再回退删除该文件夹，若文件夹里面包含子文件夹，则需先进入子文件夹，删除子文件夹里面的文件。若还包含文件夹，则重复以上步骤，直到文件夹里面为空或者只有文件时，删除文件，依次回退删除上一级。最终完成要求。

提取递归三要素：

1. 确定递归停止条件

当前是文件或者空文件夹

2. 确定递归前进

当前不是文件也不是空文件夹，则递归

3. 确定递归后退

当前是文件或者空文件夹，删除当前文件或文件夹，结束递归

关键代码：

上述例子只是递归法众多经典应用场景之一，而递归法还有其他很多经典应用场景，大家有兴趣可以自己去学习一下。递归法其他经典实例：

斐波那契数列汉诺塔问题

3.3 贪心算法实例

问题：

一台自动贩卖机，可以自动找零，找零金额有1元、2元、5元、10元、20元和50元这些面值。而每种面值的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来找零K元，至少要用多少张纸币？

问题分析：

找零K元，有很多种方式，可以全部用1元支付，若不够，用两元补充。但用这种方式，存在两个弊端：

小面额金额用太多，不利于后续其他顾客找零；一次找零太多，影响找零效率

鉴于上述两个问题，我们可以先 找零最大面额，然后依次使用次大面额的，这样可以少消耗小面额纸币，也能提高自动贩卖机的找零效率。

提取算法要素：

1. 把问题分解成多步

每次找零都为一步，直到找零结束

2. 求解每一步的最优解

每次找零都用符合条件的最大的面额

关键代码：

贪心算法有很多经典的使用场景，大家有兴趣可以自己去了解一下，这里列举出了常见的一些实例：

活动选择问题多机调度问题小船过河问题区间覆盖问题Huffman编码Dijkstra算法最小生成树

3.4 回朔法实例

问题：

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)，且每个城市之间都互通。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。

问题分析：

最终要回到起点，并且每个城市都互通，因此从那一点出发，都不影响最终的结果。假若选定一个城市，那么前往的第二个城市，有n-1个选择；选定第二个城市有n-2个选择。。。直到最后一个城市只有一种选择，从最后一个城市返回起点也只有一种选择。

从上述分析可知，每选择一个城市，后面的选择可能有1到多种，因此要求解最合适的路线，可以计算所有可能的情况，从中选择最优的结果。

因此决定一个起点，然后随便选择一个城市，直到回到原点，计算结果。然后回到有选择的城市，选择其他的城市，计算结果。若结果优于前面的结果，则认为当前最优。然后依次回退，直到所有可能的路径都走一遍，得到最优结果为止。

提取算法要素：

1.定义问题的解空间

定义一棵排列树，存储节点，以及节点权重

2. 确定搜索方式

通过深度优先搜索方式，依次回溯求解结果

关键代码：

回朔法有很多经典的使用场景，大家有兴趣可以自己去了解一下，这里列举出了常见的一些实例：

八皇后问题0-1背包问题

虽然每个算法的思想都不相同，并且每个问题可使用的算法也不唯一，但算法最终还是为程序服务。对于软件工程师而言，熟悉掌握常见的算法，在遇到问题时，你可以有更多的选择；并且可以在众多选择中找到效率更高、更简洁的处理方式。

关于作者：哆啦猫，普元移动端开发工程师，擅长Java，专注于Andriod开发。目前参与Mobile 8.0项目的开发，主要接触RN技术的应用，黏合前端代码 与Android底层之间的交互。

关于EAWorld：微服务，DevOps，数据治理，移动架构原创技术分享。