如何进行有效算法入门（避不开的算法如何吃透）

如何进行有效算法入门（避不开的算法如何吃透）(1)

作者 | Alekya Ragipally

译者 | 弯月，责编 | 屠敏

头图 | CSDN 下载自东方 IC

出品 | CSDN（ID：CSDNnews）

以下为译文：

当你使用搜索引擎（例如Google Chrome、Mozilla Firefox等）的时候，后台发生了什么？当你询问虚拟助手（例如Alexa、Google助手或Siri）的时候，后台发生了什么？它们怎么会知道答案？为何它们会显示正确答案？所有这些都要感谢算法。

每当你使用手机、计算机、笔记本电脑或计算器时，其实都在使用算法。

那么，什么是算法？

如果你想做数学运算，比如说两个数字相乘（不使用任何电子设备），那么你需要在纸上做乘法。你按照一定的规则获得正确的答案。你也可以使用耗时更少的方法来做计算。这就是算法。

算法是为执行特定的任务而设计的一组指令。

有些算法很简单，而有些则非常复杂，具体取决于你要实现的目标。

如何进行有效算法入门（避不开的算法如何吃透）(2)

算法的历史

了解历史总是有好处，因为历史可以帮助你更好地理解主题，并了解何时使用这些知识。

“算法”一词源自九世纪波斯数学家Muhammad Ibn Musa Al-Khwarizmi（代数之父），拉丁语为Algoritmi。最初算法被称为Algorismus。15世纪后期，改名为Algorithmus（源自希腊语Arithmetic）。现代英语中的Algorithm一词是于19世纪引入的。

算法在中国古代文献中称为“术”，最早出现在《周髀算经》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法，线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法：刘徽割圆术。

如何进行有效算法入门（避不开的算法如何吃透）(3)

1842年，Ada Lovelace首次编写了计算引擎的算法，因此许多人常常称她为世界上第一位计算机程序员。她为巴贝奇分析机（自动计算的机械计算机）编写了求解伯努利微分方程的算法（巴贝奇分析机由计算机之父Charles Babbage开发）。

如何进行有效算法入门（避不开的算法如何吃透）(4)

1936年，Alan Turing的图灵机首次提出了第一个以现代形式表示的算法。

如何进行有效算法入门（避不开的算法如何吃透）(5)

如何进行有效算法入门（避不开的算法如何吃透）(6)

如何表达算法？

表达算法的方法多种多样，例如自然语言、伪代码、流程图、编程语言、动态图表、控制表等等。

使用自然语言表达算法不够清晰，因此很少用于复杂或技术算法。伪代码、流程图、drakon图和控制表是表达算法的结构化方法，因为与自然语言相比，它们可以避免许多歧义。编程语言旨在以可由计算机执行的形式表达算法。

在计算机系统中，算法是由软件开发人员以他们选择的任何编程语言编写的逻辑。但是，在设计算法时，我们需要记住一些规则。其中包括：

输入：算法至少需要一个或多个输入值。如果没有给出输入，那么算法将产生什么输出呢？
输出：算法至少应产生一个输出。如果没有产生任何结果，则无需设计算法。
效率：算法应该保证高效利用计算和内存资源。产生的输出应该又正确又快。
简单性：算法不应过于复杂。
可扩展性：算法必须能够在不更改核心逻辑的情况下进行扩展。
有限性：算法必须在有限步骤后终止。假设输入错误的情况下，算法在第一步就终止，我们将永远无法得知算法有什么问题。而且，算法也不能陷入无限循环。
不依赖于编程语言：算法必须与语言无关，也就是说，它必须是可以用任何一种语言都可以实现的简单指令，但是无论任何语言，输出都应当相同。

下面，我们来构建一个简单的算法：两个数字的加法（且满足上述要求）。

第1步：开始；
第2步：声明变量num1，num2和sum；
第3步：读取值num1和num2；
第4步：将num1和num2相加，然后将值赋给sum。
第5步：显示和；
第6步：停止。

下面，为了测试这个算法，我们使用一种编程语言来实现它，我选择用Java语言来实现，你可以任意选择其他语言。

public class Addition{public static void main(String[] args) {int num1, num2, sum;Scanner sc = new Scanner(System.in);System.out.println(“Enter First Number: “);num1 = sc.nextInt;System.out.println(“Enter Second Number: “);num2 = sc.nextInt;sc.close;sum = num1 num2;System.out.println(“Sum of two numbers: “ sum);}}

输出如下：

如何进行有效算法入门（避不开的算法如何吃透）(7)

我们的算法运作良好，且满足上述要求。

算法必须高效。算法的效率取决于时间和空间。一个好的算法占用的时间更少，占用的空间也更少，我们无法时刻兼顾两者。如果减少时间，则则空间可能会增加，反之亦然。因此，我们必须妥协一方。算法的空间复杂度表示算法运行时占用或需要的总空间。时间复杂度是指算法花完成任务所需的操作数。以最少操作数执行任务的算法就是最有效的算法。此外，算法花费的时间还取决于计算机的计算速度，但是在我们考虑算法的效率率时，通常不会考虑这些外部因素。衡量算法效率的一种方法是测量算法在不同输入下找到答案所需的操作次数。

如何进行有效算法入门（避不开的算法如何吃透）(8)

如何进行有效算法入门（避不开的算法如何吃透）(9)

算法的种类

递归算法：通过重复将问题分解为同类的子问题而解决问题。
分治算法：把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
动态规划算法（又名动态优化算法）：记住过去的结果，以备将来使用。与分治算法相似，这种算法可以将复杂的问题分解相对简单的子问题，然后将解决方案保存起来，以便下次需要同一个子问题解之时直接使用，而无需再次重新计算。
贪婪算法：在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望得出结果是最好或最优的算法。该算法不能保证最终获得最佳解决方案。
暴力算法：简单明了，尝试所有的可能性，直到找到满意的解决方案为止。
回溯算法：尝试分步地去解决一个问题。如果发现其中某一步的解决方案失败，则后退一步或几步，重新开始寻找解决方案。

如何进行有效算法入门（避不开的算法如何吃透）(10)

如今，几乎每个领域都使用算法，例如数据科学、机器学习、农业、科学、运输等。算法是每个应用程序（Google Chrome与Mozilla Firefox、Uber与Ola）最大的不同之处，例如Google Chrome和Mozilla Firefox都是搜索引擎应用程序，它们提供相同的结果，但是结果的顺序有所不同，这是因为二者使用了不同的排序算法。Google的排序算法与Firefox不同。

算法无处不在，并将继续传播，算法让我们的生活更加轻松，但我们还需要考虑一些问题，例如，