算法 -{zh-hans:;zh-hant:}- 算法（），在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。 相反，启发式是一种解决问题的方法，可能没有完全指定，也可能不能保证正确或最优的结果，尤其是在没有明确定义的正确或最优结果的问题领域。例如，社交媒体推荐系统依赖于启发式，尽管在21世纪的流行媒体中被广泛称为"算法"，但由于问题的性质，它无法提供正确的结果。 早在尝试解决希尔伯特提出的判定问题时，算法的不完整概念已经初步定型；在其后的正式化阶段中人们尝试去定义“”或者“”。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年的波斯特-图灵机和艾伦·图灵1937年提出的图灵机。即使在当下，依然常有符合直觉的想法难以定义为形式化算法的情况。 算法是，包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。算法中的指令描述的是一个计算，它时从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。 一个状态到另一个状态的转移不一定是确定的。 包括随机化算法在内的一些算法，都包含了一些随机输入。 历史. 算法在中国古代文献中称为“术”，最早出现在《周髀算经》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃氏筛，线性方程组求解的高斯消元法。三国时代的刘徽给出求圆周率的算法：刘徽割圆术。 自唐代以来，历代更有许多专门论述“-{算法}-”的专著： 而英文名称「algorithm」来自于9世纪波斯数学家花拉子米（比阿勒·霍瓦里松，波斯语：--‎ ，拉丁转写：al-Khwarizmi），因为比阿勒·霍瓦里松在数学上提出了算法这个概念。「算法」原为「algorism」，即“al-Khwarizmi”的音转，意思是“花拉子米”的运算法则，在18世纪演变为「algorithm」。 欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是爱达·勒芙蕾丝（-- ）于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序，因此爱达·勒芙蕾丝被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇（-- ）未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为「well-defined procedure」缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的电脑的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。 特征. 以下是高德纳在他的著作《计算机程序设计艺术》里对演算法的特征归纳： 基本要素. 算法的核心是建立问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。 常用设计模式. 完全遍历法和不完全遍历法：在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。 分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。 线性规划法：见条目。 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。 常用实现方法. 递归方法与迭代方法 顺序计算、并行计算和分布式运算：顺序计算就是把形式化算法用程序设计语言进行单线程序列化后执行。 确定性算法和非确定性算法 精确求解和近似求解 形式化算法. 算法是电脑处理信息的本质，因为计算机程序本质上是一个算法来告诉电脑确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，会从输入装置或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。 复杂度. 时间复杂度. 算法的时间复杂度是指算法需要消耗的时间资源。一般来说，电脑算法是问题规模formula_1的函数formula_2，算法的时间复杂度也因此记做 ：formula_3 算法执行时间的增长率与formula_2的增长率正相关，称作，简称时间复杂度。 常见的时间复杂度有：常数阶formula_5，对数阶formula_6，线性阶formula_7，线性对数阶formula_8，平方阶formula_9，立方阶formula_10，…，formula_11次方阶formula_12，指数阶formula_13。随着问题规模formula_1的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 空间复杂度. 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 实现. 算法不单单可以用计算机程序来实现，也可以在人工神经网络、电路或者机械设备上实现。 示例. 求最大值演算法. 这是算法的一个简单的例子。 我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数位看成是一颗豆子的大小，可以将下面的算法形象地称为「捡豆子」： 下面是一个形式算法，用ANSI C代码表示 int max（int *array, int size） int mval = *array; int i; for （i = 1; i mval） mval = array[i]; return mval; 求最大公约数演算法. 求两个自然数的最大公约数 设两个变量formula_15和formula_16 用ANSI C代码表示 //交换2数 void swapi（int *x, int *y） int tmp = *x; *x = *y; *y = tmp; int gcd（int m, int n） int r; do if （m 参考文献. 参阅.