算法是什么？解决问题的一系列明确步骤

算法（Algorithm）是为了解决某一类问题而设计的一系列明确、有限的操作步骤。只要按照这些步骤一步步地执行，就能从给定的输入得到想要的输出。菜谱就是一个生活中的“算法”：准备哪些食材是输入，按照步骤切菜、下锅、调味，最后得到一道菜，就是输出。

名字的由来

“算法”的英文 algorithm 来源于 9 世纪波斯数学家穆罕默德·本·穆萨·花拉子米（al-Khwarizmi）的名字。他写了一本介绍印度数字和十进制计算方法的书，这本书的拉丁文译本在欧洲广泛流传，他名字的拉丁化写法后来就演变成了表示“计算方法”的词语。代数（algebra）一词也来自他的另一本著作。实际上，算法的思想比这还要古老得多：公元前 300 年左右，古希腊数学家欧几里得记载了求两个整数最大公约数的方法，也就是辗转相除法，它被认为是最早的算法之一，至今仍在使用；中国古代的《九章算术》中也记载了大量的计算方法。

算法的特性

计算机科学家高德纳在他的经典著作《计算机程序设计艺术》中总结了算法的五个重要特性：有穷性，算法必须在执行有限的步骤之后结束，不能无休止地运行下去；确定性，每一个步骤都必须有明确的含义，不能有歧义，同样的输入一定得到同样的结果；可行性，每一个步骤都能够通过基本的操作在有限的时间内完成；输入，算法有零个或多个输入；输出，算法有一个或多个输出。

需要注意，算法和程序不完全是一回事：算法是解决问题的思路和步骤，可以用自然语言、流程图或伪代码来描述；程序是用某种具体的编程语言把算法实现出来的代码。同一个算法，可以用不同的编程语言写成不同的程序。

怎么评价一个算法的好坏

解决同一个问题，往往有很多种不同的算法，它们的效率可能相差巨大。评价算法主要看两个方面：时间复杂度，算法运行所需的时间随着输入规模的增大而增长的速度；空间复杂度，算法运行所需的存储空间随着输入规模的增长情况。它们通常用“大 O 表示法”来描述。比如在一百万个已经排好序的数字中查找某一个数，如果从头到尾一个个地找，最坏要找一百万次；而用二分查找，每次和中间的数比较、排除一半，最多只需要找约 20 次。当数据量很大时，好的算法和差的算法之间的差距可能是几秒钟和几百年的区别。

常见的算法类型

排序算法，比如快速排序、归并排序；搜索算法，比如二分查找、广度优先搜索、深度优先搜索；图算法，比如计算最短路径的迪杰斯特拉算法；以及动态规划、贪心算法、分治算法等解决问题的通用策略；还有加密算法、压缩算法等。

机器学习算法

传统的算法由人来设计每一个步骤，明确地告诉计算机怎么做。而机器学习算法有所不同：它是一种“学习的算法”，人设计的是让计算机从数据中自动学习规律的方法，比如梯度下降、反向传播、决策树的构建方法，而具体的判断规则是计算机从大量数据中学出来的。在日常的语境中，人们常说的“推荐算法”“平台算法”，往往指的是基于机器学习的推荐和排序系统。我国在 2022 年施行的《互联网信息服务算法推荐管理规定》对这类算法的使用进行了规范，要求保障用户的知情权和选择权。