1.1　建立算法初步概念

很多开发者都知道“程序=数据结构+算法”这个著名的公式，但却并不真正明白算法的定义或者概念。

1.1.1　什么是算法

究竟什么是算法（algorithm）呢？从字面意义上理解，算法即用于计算的方法，通过这种方法可以达到预期的计算结果。

此外，在一般的教科书或者字典中也有关于算法的专业解释，例如，算法是解决实际问题的一种精确描述方法、算法是对特定问题的求解步骤的一种精确描述方法等。目前，被广泛认可的算法的专业定义是，算法是模型分析的一组可行的、确定的和有穷的规则。

其实，通俗地讲，算法可以理解为一个完整的解题步骤，由一些基本运算和规定的运算顺序构成。通过这样的解题步骤可以解决特定的问题。从计算机程序设计的角度看，算法由一系列求解问题的指令构成，能够根据规范的输入，在有限的时间内获得有效的输出结果。算法代表了用系统的方法来描述解决问题的一种策略机制。

举一个例子来分析算法是如何在现实生活中发挥作用的。最典型的例子就是统筹安排，假设有3件事（事件A、事件B和事件C）要做：

・做事件A需要耗费5分钟；

・做事件B需要耗费5分钟但需要15分钟的时间才可以得到结果，如烧水等待水开的过程；

・做事件C需要耗费10分钟。

那么应该怎样来做这三件事情呢？一种方法是依次做，如图1-1所示，做完事件A，再做事情B，最后做事情C。这样，总的耗时为5+（5+15）+10=35分钟，这显然是浪费时间的一种方法。

在实际生活中比较可取的方法是，先做事件B，在等待事件B完成的过程中做事件A和事件C。这样，等待事件B完成的15分钟正好可以完成事件A和事件C。此时，总的耗时为5+15=20分钟，效率明显提高，如图1-2所示。

在上述例子中提到的两种方法就可以看作两种算法。第一种算法效率低，第二种算法效率高，但都达到了做完事情的目的。从这个例子可以看出，算法也是有好坏区别的，好的算法可以提高工作的效率。算法的基本任务是针对一个具体的问题，找到一个高效的处理方法，从而获得最佳的结果。

一个典型的算法一般都可以从中抽象出5个特征：有穷性、确切性、输入、输出和可行性。下面结合上述例子来分析这5个特征。

・有穷性：算法的指令或者步骤的执行次数是有限的，执行时间也是有限的。例如，在上面的例子中，通过短短的几步就可以完成任务，而且执行时间都是有限的。

・确切性：算法的每一个指令或者步骤都必须有明确的定义和描述。例如，在上面的例子中，为了完成三件事情的任务，每一步做什么事情都有明确的规定。

・输入：一个算法应该有相应的输入条件，用来刻画运算对象的初始情况。例如，在上面的例子中，有三个待完成的事件（事件A、事件B和事件C），这三个事件便是输入。

・输出：一个算法应该有明确的结果输出。这是容易理解的，因为没有得到结果的算法毫无意义。例如，在上面的例子中，输出结果便是三件事情全部做完了。

・可行性：算法的执行步骤必须是可行的，且可以在有限时间内完成。例如，在上面的例子中，每一个步骤都切实可行。其实，无法执行的步骤也是毫无意义的，解决不了任何实际问题。

目前，算法的应用非常广泛，常用的算法包括递推算法、递归算法、穷举算法、贪婪算法、分治算法、动态规划算法和迭代算法等多种。本书将逐步向读者展示各种算法的原理和应用。

1.1.2　算法的发展历史

关于算法的起源，可以追溯到我国古代公元前1世纪的《周髀算经》，它是算经的十书之一，原名《周髀》，主要阐述古代中国的盖天说和四分历法。在唐朝的时候，此书被定为国子监明算科的教材之一，并改名为《周髀算经》。算法在我国古代称为“演算法”。《周髀算经》中记载了勾股定理、开平方问题、等差级数问题等，其中用到了相当复杂的分数算法和开平方算法等。在随后的发展中，出现了割圆术、秦九韶算法和剩余定理等一些经典算法。

在西方，公元9世纪波斯数学家al-Khwarizmi提出了算法的概念。“算法”最初写为algorism，意思是采用阿拉伯数字的运算法则。到了18世纪，算法正式命名为algorithm。由于汉字计算的不方便，导致我国古代算法的发展比较缓慢，而采用阿拉伯数字的西方国家则发展迅速。例如，著名的欧几里德算法（又称辗转相除法）就是典型的算法。

在历史上，Ada Byron被认为是第一个程序员。她在1842年编写的巴贝奇分析机上的伯努利方程的求解算法程序虽然未能执行，但奠定了计算机算法程序设计的基础。

后来，随着计算机的发展，在计算机中实现各种算法已成为可能。算法在计算机程序设计领域又得到了重要发展。目前，几乎所有的程序员编程时，无论采用何种编程语言，都需要与算法打交道。

1.1.3　算法的分类

算法是一门古老且庞大的学科，随着历史的发展，演化出多种多样的算法。按照不同的应用和特性，算法可以分为不同的类别。

1）按照应用来分类

按照算法的应用领域，即解决的问题，算法可以分为基本算法、数据结构相关的算法、几何算法、图论算法、规划算法、数值分析算法、加密/解密算法、排序算法、查找算法、并行算法和数论算法等。

2）按照确定性来分类

按照算法结果的确定性来分类，算法可以分为确定性算法和非确定性算法。

・确定性算法：这类算法在有限的时间内完成计算，得到的结果是唯一的，且经常取决于输入值。

・非确定性算法：这类算法在有限的时间内完成计算，但是得到的结果往往不是唯一的，即存在多值性。

3）按照算法的思路来分类

按照算法的思路来分类，算法可以分为递推算法、递归算法、穷举算法、贪婪算法、分治算法、动态规划算法和迭代算法等多种算法。