“常见经典算法”分析与研究

刘放美+蔡增玉+付长宽

摘 要： 经典算法是计算机专业核心课程之一。计算机算法的优劣，对于计算机硬件的利用和系统的性能具有重要的影响。算法也是计算机科学中重要的理论之一。本文对递归算法、分治算法、动态规划算法、贪心算法等经典的算法进行研究，着重阐述算法的设计思想、优缺点及其应用，并对算法的发展进行了探索。

关键词： 经典算法； 设计思想； 优缺点； 应用； 展望

中图分类号：TP301 文献标志码：A 文章编号：1006-8228（2017）11-58-03

Analysis and study on common classical algorithms

Liu Fangmei1， Cai Zengyu2， Fu Changkuan1

（software engineering college， Zhengzhou University of Light Industry， Zhengzhou， Henan 450002， China；

2. School of Computer and Communication Engineering， Zhengzhou University of Light Industry）

Abstract： Classical algorithm is one of the core courses in computer science. Computer algorithm has great effect on the performance and use of computer hardware system. Algorithm is also one of the most important theories in computer science. In this paper， the classical algorithms such as the recursive algorithm， partition algorithm， dynamic programming algorithm and greedy algorithm etc. are studied， the design idea， advantages and disadvantages， and the applications of the algorithms are emphatically expounded， and the development of the algorithms is explored.

Key words： classical algorithm； design idea； advantages and disadvantages； prospect

0 引言

算法是通过基本运算及运算规定的运算顺序所构成的完整的解题步骤。算法要求设计好有限的、确切的计算序列，通过设计好的步骤和计算序列可以解决同类问题。要设计出好的算法，就必须对存在的问题有深入细致的了解，还要有独特的思考方式，只有如此，才能有奇妙的算法思想，这正是解决问题的关键。当解决问题的方式有多种多样时，就会存在不同的算法思想，而它们在解决问题时有各自的优势和不足，我们根据需求，选择出最佳方案，用最合适的算法来解决现实中的问题，并逐步探索研究未来算法的方向，这便是我们探究与发现的初衷[1]。

1 常见经典算法分析

1.1 递归算法

递归算法是在一个函数定义或者声明的过程中直接或者间接地又调用自身的一种方法。递归算法基本思想是，把一个复杂的大问题转化为规模较小且相似的子问题来解决，可以用很少的代码来解决多次重复计算的问题，节省了运算时间。对于一些产生情况非常多的算法问题，利用穷举法将是非常麻烦且不明智的，如果利用递归可以解决的话，就可以实现交换元素，函数调用函数，最终得到结果。这避免了重复计算，节约了运算时间。

递归的缺陷是解决问题的运行效率非常低[2]，原因在于在递归调用的过程中，系统会为每一层的返回点，局部变量等开辟了堆栈来存储，而且如果出现递归调用次数过多，会出现堆栈溢出的问题，这也是很可怕的。

我们应该知道递归都用来解决哪些问题，首先，它可以解决一些数据的定义，其次，它可以实现一些问题求解，而且，数据的结构形式也可以按照递归定义。按照递归的这些适用条件，我们很容易的想到，它可以解决我们经常见到的Fibonacci函數，回溯算法，以及树的遍历，图的搜索等相关的问题。

1.2 分治算法

分治算法是把一个复杂的问题分成了多个子问题，逐步细分，直到子问题可以直接求解，而子问题的解的合并就是原问题的解。分治法的基本思想是把一个不容易解决的子问题分为规模较小的相似问题，以便于可以直接求解，递归地解决这些子问题，再将得到的子问题的解合并，就得到了原问题的解。

当需要解决一个输入规模（n）很大的问题时，直接处理往往比较困难或者根本无法求解，我们希望把输入规模缩小，即分成很多份，分别去解决，并且这些小问题容易合起来从而解决整个问题。这便是分治的优势所在，简单高效。但是分治法的合并步骤并不是很容易的，有的问题的合并方法比较明确，而有的问题的合并方法比较复杂，可能还需要讨论多种合并方案，这也是一个小缺陷。

分治算法在一些应用中是简单有效的，只要遇到的问题可以分解为很多小规模的相似的子问题，且子问题独立无依赖，最后又可以合并子问题的解，就可以使用分治算法[3]。在一些经典的排序问题中，分治法起到了至关重要的作用。

1.3 动态规划算法

动态规划是一个过程，每次决策都依赖于当前的状态，然后会引起状态的转移，如何决策就是在变化中产生出来的，这样的多阶段最优化决策解决问题的过程就是动态规划。动态规划把要求解的问题分成了很多子问题，从简单的子问题入手，求出它们的解，然后再得出最终答案。与分治算法不同的是，动态规划算法不是递归地求解每一个子问题，而是从简单问题的解入手，逐步求解，最后再求出原问题的解，动态规划的高明之处就在于，它不会重复求解某些重复出现的子问题，即一些重叠子问题，所以计算的效率是非常高的。利用动态规划，可以保存已解决的子问题的答案，在需要的时候再加以利用，这样减少了大量的重复计算，节省了时间。求解过程就是先找出最优解的结构，递归定义一个最优解的值，然后以自底向上的方式计算出最优解的值，根据计算最优解的值的信息，构造出一个最优解。但是动态规划在存储中间过程产生的结果需要大量的空间，这是动态规划的明显缺点，以空间换时间。endprint

对于动态规划算法来说，它要依赖于问题本身所具有的两个重要性质，一个是最优子结构性质，另一个是子问题重叠性质[4]。只有提前满足了这两个条件，动态规划算法才能发挥它的高效作用。动态规划算法的应用十分广泛，典型应用有矩陣连乘，在解决矩阵连乘问题中，先从最简单的两个矩阵相乘开始，再看三个，四个，从而得到如何进行乘法运算，可以让相乘的次数最少，最后我们可以求出矩阵连乘的次数和它们如何相乘。正是以大化小，才使解决问题更加方便。动态规划还经常应用在最长公共子序列、最大字段和数字三角形问题上。

1.4 贪心算法

贪心算法是指在求解问题时不从整体上考虑，只做出当前最好的选择，也就是局部最优解。贪心算法的基本思想是找出整体中局部的最优解，然后根据这些最优解来得到整体的最优解。在求解最优化问题算法中，一般会包括一系列的求解步骤，每一个求解步骤中都有一个选择，然后得到问题的一个解。贪心算法在具体求解问题时是非常简单有效的，有时候虽然不能得到最优解，但是可以得到近似解。贪心算法只选择当前看起来最好的选择，而不去考虑它整体是不是最好的，正确的运用贪心算法，应该保证贪心策略无后效性，即：某个状态以后过程不影响以前的状态，只和当前状态有关。贪心算法对于解决很多问题都是非常有效的，因为局部最优解很容易找到，所以简单易懂，效率较高，对于许多问题都可以得到整体最优解。贪心算法的缺点主要表现在它的“非理想性”。因为我们找到的问题往往并不一定符合贪心算法的适用条件，即使达到了局部最优，也很难得到我们想要的结果。贪心算法要想有效，就必须满足问题的约束，达到局部最优的条件。如图1所示的单源路径问题，虽然我们无法一眼看出最优的结果，不知道该从哪一步走，但我们可以根据相邻顶点的路径来找出当前最好的选择，这便是先从局部最优开始[5]。

我们可以用dist[i]来记录当前的每个顶点的最短路径，再从结果中找出具有最短路径的顶点，写入S集合中，等把所有的顶点都加入到了S集合中，dist就记录了源顶点到其他顶点最短的路径长度。如表1所示：

此外，贪心算法还广泛地应用于活动安排问题，背包问题，最优装载问题等。

1.5 经典算法的比较

经典算法有很多，每个算法都有其独到之处。本文对递归算法，分治算法，动态规划算法和贪心算法进行归纳分析，总结了各自的优缺点，如表2所示。要想真正地将算法用到恰到好处，就必须根据应用场景，在相应的条件下使用合适算法解决实际问题[6]。

2 未来展望

很多人认为，未来算法的重要性会变低，但是作为计算机科学领域最重要的基石之一的算法，它的重要性是会日益加强的。而且算法也将不局限于计算机和网络，它所应用的范围也会越来越大。

2.1 算法在未来的重要性

在很多程序员看来，编程语言最值得关注，其实随着时代的发展，算法会变得越来越有用，虽然编程语言的种类越来越多，有些编程语言由冷门到热门，然而有些也会从热门变为冷门，技术在不停地更新换代，但是有些东西是不变的，例如算法，数据结构，编程原理，关系型数据库原理，计算机体系结构等等。未来编程，算法将会是一种内在的“修养”，没有算法的思想和理论，就不可能成为真正的程序员。

2.2 算法在未来的应用

如今计算机已经全面普及，价格也很低廉。当在激烈的竞争中，用户体验成为了关键，用算法去设计各种应用，是一个必然的选择。在存储方面，大数据存储是关键问题，算法能有效的提高大数据存储的效率。在科学研究方面，无论是三维模型还是数据处理，都会需要很大的计算量，都要靠算法来解决。例如Google每天都会处理数以亿计的搜索，存储几千万用户的数据，通过互联网将巨量的信息提交给每个用户，很显然，如果没有找到好的算法，这些是不可能完成的。所以Google数据中心使用的是超大型并行计算机，让并行算法在并行计算的环境下执行，使处理请求速度得到飞跃式的提升。

2.3 算法前景

算法的作用在未来计算机的发展中不可估量，不仅在大数据和云计算方面，也用于解决实验数据的处理和存储，还用来研究人类基因，发明新的医疗方式，可以保障国家网络安全，预测天灾的发生等。算法在未来的机遇和挑战并存的环境中是不可或缺的，是不可以替代的。我们要用发展的眼光来看待算法，与时俱进，不可轻视它，冷落它，须始终保持一颗对算法探索研究的心，争取利用算法来造福美好的未来。

3 总结

本文对常用经典算法进行了概括与分析，探究了算法的设计思想与优缺点，并根据算法的具体应深入探讨算法。从分析和研究我们可以看出，在不同的情况下，应该选择不同的算法。同时，我们也能发现在复杂的问题面前，一个正确高效的算法是非常重要的，每一个算法都有自己的优缺点，在算法选择时，要考虑算法本身的特性。面对复杂的问题，要具体问题具体分析，将复杂的问题简单化，将算法的思想与解题步骤巧妙地联系在一起，用科学有效的方法来解决问题，这是学习的意义所在。算法有着美好而又远大的前景，还需要我们独具慧心，发掘算法的潜力，造福我们的生活。

参考文献（References）：

[1] 陈德裕，杭月芹.数据结构中经典算法的教学研究[J].计算机

时代，2009.6：3-4

[2] 袁劲松，杨伟明.递归算法设计及效率分析[J].计算机与数字

工程，2007.2：12-13

[3] 李健勇，李晔，刘艳红，张杰，李建春，黄道颖.任意数量选手的

循环赛赛程分治算法[J].郑州轻工业学院学报（自然科学版），2007.4：26-27

[4] 宛楠，张义.动态规划算法分析[J].长江大学学报（自然科学

版），2013.7：3-6

[5] 常友渠，肖贵元，曾敏.贪心算法的探讨与研究[J].重庆电力高

等专科学校学报，2008.3：31-32

[6] 欧阳圣，胡望宇.几种经典搜索算法研究与应用[J]. 计算机系

统应用，2011.5：16-17endprint