下载文档原格式
1.1.1 算法的概念
算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或
输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
〖算法的历史〗
“算法” (algorithm)来自于9世纪波斯数学家比阿勒•霍瓦里松的名字al-Khwarizmi ,比阿勒•霍瓦里松在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm" 第一次编写算法是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。因为"well-defined procedure" 缺少数学上精确的定义，19世纪和
20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学
家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。
〖算法的特征〗
一个算法应该具有以下五个重要的特征:
有穷性：一个算法必须保证执行有限步之后结束；
确切性：算法的每一步骤必须有确切的定义；
输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0
个输入是指算法本身定除了初始条件；
输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没
有输出的算法是毫无意义的；
可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
〖形式化算法〗
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
〖算法的实现〗
算法不单单可以用计算机程序来实现，也可以在神经网络、电路或者机械设备
上实现。
•例子
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中
的每一个数字看成是一颗豆子的大小，可以将下面的算法形象地称为“捡豆
子”：
首先将第一颗豆子放入口袋中。
从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的
还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。
最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法，用近似于编程语言的伪代码表示
给定：一个数列“list"，以及数列的长度"le ngth(list)"
largest = list[1]
for coun ter = 2 to len gth(list):
if list[co un ter] > largest:
largest = list[co un ter]
print largest
符号说明：
=用于表示赋值。即：右边的值被赋予给左边的变量。
List[counter] 用于表示数列中的第counter项。例如：如果counter的值是5,
那么List[counter] 表示数列中的第5项。
<=用于表示“小于或等于”。
==例子==
求两个自然数的最大公约数设两个变量M和N 1.如果M < N,则交换M和N
2.以N除以M,得到余数R
3.判断R = 0,正确则N即为“最大公约数”，否则下一步
4.将N赋值给M,将R赋值给N，重做第一步。用“ Basic代码”表示——
If M < N The n Swap M,N Do While R <> 0
R = M Mod N
M = N
N = R
Loop Print R
〖算法设计和分析的基本方法〗
分治法：字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）……
动态规划：动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
贪心法（亦作饕餮法）：就是一种在每一步选择中都采取在当前状态下最好/优的选择，从而希望导致结果是最好/优的算法。贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一
般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
〖算法的分类〗
•基本算法〔枚举搜索（深度优先搜索广度优先搜索启发式搜索遗传算法）〕•数据结构的算法
•数论与代数算法
•计算几何的算法（凸包算法）
•图论的算法（哈夫曼编码树的遍历最短路径算法最小生成树算法最小树形图网络流算法匹配算法）
•动态规划
•其他（数值分析加密算法排序算法检索算法随机化算法）还可以分成串行算法、并行算法。
〖算法的复杂性〗
算法的复杂性是算法效率的度量，在评价算法性能时，复杂性是一个重要的依据。算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂性越高；所需要的资源越少，表明该算法的复杂性越低。
计算机的资源，最重要的是运算所需的时间和存储程序和数据所需的空
