共计 3361 个字符，预计需要花费 9 分钟才能阅读完成。
算法是指实现一个工作所须要的具体步骤和办法。也就是说给定初始状态或输出数据，通过计算机程序的无限次运算，可能得出所要求或冀望的终止状态或输入数据。
编程界的“Pascal 之父”Nicklaus Wirth 有一句人尽皆知的名言：“算法 + 数据结构 = 程序”。（Algorithm+Data Structures=Programs），可见算法对程序的重要性。
本文从算法的根本定义登程，具体解读了算法的倒退历程、次要特色、掂量指标和算法设计的根本办法，供大家学习参考。
1. 算法的根本定义
百科百科对算法的定义是：算法（Algorithm）是指解题计划的精确而残缺的形容，是一系列解决问题的清晰指令，算法代表着用零碎的办法形容解决问题的策略机制。也就是说，可能对肯定标准的输出，在无限工夫内取得所要求的输入。
一句话概括一下，算法就是解决问题的操作步骤。
2. 算法的倒退历程
在我国现代，算法被称为“演算法”，对于算法的起源最早能够追溯到我国现代公元前 1 世纪的《周髀算经》，是算经的十书之一，原名《周髀》，次要论述现代中国的盖天说和四分历法。在唐朝的时候，此书被定为国子监算科的教材之一，并改名为《周髀算经》。《周髀算经》中记录了勾股定理、开平方问题、等差级数等问题，其中用到了相当简单的分数算法和开平方算法等。在随后的倒退中，呈现了割圆术、秦九昭算法和残余定理等一些经典算法。
在东方，算法（algorithm）一词最早来源于 9 世纪波斯数学家花拉子米（花拉子米是代数与算术的创建人，被誉为“代数之父”，所著《代数学》一书，最早给出了一次和二次方程的个别解法），花拉子米的拉丁文译名是“Algoritmi”，英文对“算法”原译为“algorism”，意思是花拉子米的运算法令，指的是用阿拉伯数字进行算术运算的过程，在 18 世纪演变为“algorithm”。
阿拉伯数学家花拉子米
世界上第一个算法
公元前 300 年，“几何之父”欧几里得提出了人类史上第一个算法——欧几里得算法，又称辗转相除法，是求最大公约数的一种办法。它的具体做法是: 用较大数除以较小数，再用呈现的余数 (第余数) 去除除数，再用呈现的余数 (第二余数) 去除第一余数，如此重复，直到最初余数是 0 为止。如果是求两个数的最大公约数，那么最初的除数就是这两个数的最大公约数。
辗转相除法举例:
求 10，25 的最大公约数:
25/10=2……5
10/5=2……0
所以 10，25 的最大公约数为 5
辗转相除法代码实现:
int gcd(a, b)
[return b == 0 ? a : gcd(b, a % b); }
// 当余数为 0 时，最大公约数就是 a，否则持续往下递归世界上第一个算法程序
“If I should see you,after long year.How should I greet, with tears, with silence. “ 这是英国著名诗人拜伦的诗句，而世界上第一位程序员阿达·洛芙莱斯（Ada Lovelace），就是这位著名诗人的女儿，她编写了世界上第一个算法程序。1842 年，Ada 为巴贝奇剖析机编写求解伯努利方程的程序，写作了第一份“程序设计流程图”，被珍视为“第一位给计算机写程序的人”。因为查尔斯·巴贝奇(Charles Babbage) 未能实现他的巴贝奇剖析机，这个算法未能在巴贝奇剖析机上执行。
这张写满数学算法的巨幅图表，被视为“第一个计算机程序”，由埃达·洛夫莱斯编写，发表于 1843 年的一篇对于“剖析机”的文章中。埃达对此给出精准形容如下：“这张表显示了运算过程中，机器各局部的所有间断变动。”尽管这个算法未能实现，但 Ada 对计算机科学的奉献毋庸置疑，1953 年，阿达之前对查尔斯·巴贝奇的《剖析机概论》所留下的笔记被从新颁布，并被公认对古代计算机与软件工程造成了重大影响。
“软件之母”Ada Lovelace
图灵机
20 世纪的英国数学家图灵提出了驰名的图灵论题，并提出一种假想的计算机的形象模型，这个模型被称为图灵机。
图灵机，又称图灵计算机，是指一个形象的机器，行将人们应用纸笔进行数学运算的过程进行形象，由一个虚构的机器代替人类进行数学运算。
它有一条有限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的色彩。有一个机器头在纸带上移来移去。机器头有一组外部状态，还有一些固定的程序。在每个时刻，机器头都要从以后纸带上读入一个方格信息，而后联合本人的外部状态查找程序表，依据程序输入信息到纸带方格上，并转换本人的外部状态，而后进行挪动。
图灵机是可被视作任意解决无限数学逻辑过程的机器，能够用来模仿任何算法。图灵机的呈现解决了算法定义的难题，图灵的思维对算法的倒退起到了重要的作用。
3. 算法的重要特色
一个算法应该具备以下五个重要的特色：
·有穷性（Finiteness）算法的有穷性是指算法必须能在执行无限个步骤之后终止；
·确切性 (Definiteness) 算法的每一步骤必须有确切的定义；
·输出项 (Input) 一个算法有 0 个或多个输出，以刻画运算对象的初始状况，所谓 0 个输出是指算法自身定出了初始条件；
·输入项 (Output) 一个算法有一个或多个输入，以反映对输出数据加工后的后果。没有输入的算法是毫无意义的；
·可行性 (Effectiveness) 算法中执行的任何计算步骤都是能够被合成为根本的可执行的操作步骤，即每个计算步骤都能够在无限工夫内实现（也称之为有效性）。
4. 算法的评定
算法的复杂性是算法效率的度量，在评估算法性能时，复杂性是一个重要的根据。算法的复杂性的水平与运行该算法所须要的计算机资源的多少无关，所须要的资源越多，表明该算法的复杂性越高: 所须要的资源越少，表明该算法的复杂性越低。
计算机的资源，最重要的是运算所需的工夫和存储程序和数据所需的空间资源，算法的复杂性有工夫复杂性和空间复杂性之分。
评定一个算法的优劣能够从以下 5 个方面进行掂量：
1）工夫复杂度
是对一个算法在运行过程中长期占用存储空间大小量度。
2）空间复杂度
程序运行时基本操作所执行的次数。
3）正确性
算法的正确性是评估一个算法优劣的最重要的规范。
4）可读性
算法的可读性是指一个算法可供人们浏览的容易水平。
5）鲁棒性
鲁棒性是指一个算法对不合理数据输出的反馈能力和解决能力，也称为容错性。
5. 算法设计和剖析的根本办法：
1）递归和递推。递归和递推是学习算法设计的第一步。递归算法是把大问题分解成绝对较小的问题的过程，而递推就是从小问题逐渐推导出大问题的过程。无论递归还是递推，都应该有初始状态。
2)搜寻、枚举及优化剪枝。搜寻在所有算法中既是最简略也是最简单的算法。说它简略，是因为算法自身并不简单，实现容易: 说它最简单，是因为要对搜寻的范畴进行肯定的管制，不然就会呈现超时等问题。搜寻技术次要包含广度优先搜寻和深度优先搜寻。当其余算法都无奈对问题进行求解时，搜寻或者是惟一可用的办法。搜寻是对问题的解空间进行遍历的过程。有时问题解空间相当宏大，齐全遍历解空间是不事实的，此时就必须充沛挖掘问题所蕴含的约束条件，在搜寻过程中利用这些条件进行剪枝，从而缩小搜寻量。
3）分治法。字面上的解释是“分而治之”，就是把一个简单的问题分成两个或更多的雷同或类似的子问题，再把子问题分成更小的子问题 ….. 直到最初子问题能够简略的间接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的根底，如排序算法(疾速排序，归并排序)，傅立叶变换(疾速傅立叶变换)……
4）动静规划法。动静布局在查找有很多重叠子问题的状况的最优解时无效。它将问题重新组合成子问题。为了防止屡次解决这些子问题，它们的后果都逐步被计算并被保留，从简略的问题直到整个问题都被解决。因而，动静布局保留递归时的后果，因此不会在解决同样的问题时破费工夫。
5）贪婪算法(亦作饕餮法)。就是一种在每一步抉择中都采取在以后状态下最好 / 优的抉择，从而心愿导致后果是最好! 优的算法。贪婪法能够解决一些最优性问题，如: 求图中的最小生成树、求哈夫曼编码 ….. 对于其余问题，贪婪法般不能失去咱们所要求的答案。一旦一个问题能够通过贪婪法来解决，那么贪婪法个别是解决这个问题的最好方法。因为贪婪法的高效性以及其所求得的答案比拟靠近最优后果，贪婪法也能够用作辅助算法或者间接解决一些要求后果不特地准确的问题。