算法是为执行计算或解决某一类问题而精确定义的过程。它描述了一系列操作，将符合要求的输入转换为满足既定要求的结果。在经典意义上，解决问题的算法必须对每个有效输入都能在有限步骤后终止。算法在数学和计算机科学中占据核心地位，但并不一定依赖电子设备：人也可以用纸笔执行算术算法。算法是一种抽象方法，不同于实现它的具体程序或机器。(xlinux.nist.gov)
历史发展
“算法”一词源自九世纪数学家花拉子米姓名的拉丁化形式。他的著作讲解了如何使用印度-阿拉伯数字系统进行计算。他的算术论著的拉丁文译本帮助将这些方法传入中世纪欧洲。与之相关的术语 algorism 指使用这些数字进行计算；而 algorithm（算法）的现代含义已超出算术的范围，涵盖一般的计算过程。(mathshistory.st-andrews.ac.uk)
计算过程的历史比“算法”一词更为久远。与欧几里得相关的欧几里得算法通过反复进行带余除法，求出两个正整数的最大公约数。二十世纪，计算模型为算法研究奠定了形式化基础。在1936年提交的论文中，艾伦·图灵提出了如今称为图灵机的抽象机器，使有效计算及其局限性的问题能够用数学语言表述。(xlinux.nist.gov)
规约与表示
算法问题规定了有效的输入和可接受的输出。例如，排序问题要求输出恰好包含输入中的全部元素，并按指定顺序排列。算法提供了得到这种输出的方法；它必须适用于规定的整个输入域，而不只是某些选定的示例。不同算法可以解决同一个问题，但所需资源可能不同。(live.ocw.mit.edu)
算法可以用自然语言、方程、伪代码或编程语言来描述。伪代码表达算法的基本操作，而不拘泥于某种特定语言的语法。算法通常结合顺序执行的指令、条件分支和重复操作。递归通过同一计算问题的更小实例来表达计算，并以基本情形作为停止条件。数据结构规定信息如何组织和访问；数据结构的选择可能显著影响效率。(xlinux.nist.gov)
对于正整数 (a) 和 (b)，欧几里得算法反复将 ((a,b)) 替换为 ((b,a\bmod b))，直到 (b=0)，然后返回 (a)。例如，从 ((48,18)) 开始，依次得到 ((18,12))、((12,6)) 和 ((6,0))，因此结果为6。这一变换保持公约数不变，同时每个非零余数都小于前一步的除数。这些性质解释了算法为什么正确，以及为什么能够终止。(xlinux.nist.gov)
正确性与效率
正确性关注算法是否满足其规约。数学证明必须确立算法对每个允许的输入都满足规约。对于递归过程，证明通常使用数学归纳法；对于迭代过程，则常使用循环不变式，即在反复执行过程中始终保持成立的性质。测试通过可以为某些具体执行情况提供证据，但通常不能证明算法在不受限制的整个输入域上都正确。(live.ocw.mit.edu)
计算复杂度衡量资源需求随输入规模增长而变化的情况。时间复杂度统计在指定计算模型下执行的操作次数；空间复杂度衡量内存使用量。输入规模可以指记录的数量、图中的顶点数，或编码一个整数所需的位数。因此，将算术运算视为常数时间操作是一种建模假设，而不是普遍成立的事实。(live.ocw.mit.edu)
大O记号用于表示渐近上界，忽略常数因子和低阶项。二分查找通过反复将剩余区间减半，在已排序的数组中查找某个值；对于 (n) 个元素，需要 (O(\log n)) 次比较。然而，在链表中，访问相应元素可能需要线性规模的遍历。这说明，必须结合数据的表示方式来理解操作次数。(web.stanford.edu)
最坏情况分析考虑给定规模下资源需求最大的输入。平均情况分析假定输入服从某种分布，而随机化算法的期望运行时间则可以针对固定输入，考察算法内部的随机选择。这些是不同的度量，不一定得到相同的界。(web.stanford.edu)
设计策略
算法设计中经常使用以下几种策略：
- 穷举法：系统地检查候选解。
- 分治法：将问题拆分为更小的实例，分别求解，再合并结果。
- 动态规划：保存子问题的解，使同一子问题再次出现时不必重新计算。
- 贪心法：每一步都作出局部最优的选择。只有当问题具有适当的结构性质时，这些选择才能得到全局最优解。(live.ocw.mit.edu)
随机化算法在执行过程中引入随机选择。拉斯维加斯算法总是返回正确答案，但运行时间可能变化；蒙特卡洛算法则可能以受控的概率返回错误答案。对这类算法的分析使用概率来量化对运行时间或错误率的保证。因此，随机化并不只是指过程未被明确规定或无法预测。(web.stanford.edu)
算法计算的局限
并非每个表述精确的问题都能用算法解决。停机问题问的是：任意一个程序在给定输入后，最终是否会停止。不存在一种算法，能够对每一组程序与输入都给出正确答案并终止。这并不妨碍人们证明某些特定程序或受限类别的程序能够终止。不可判定性与计算成本高昂是不同的概念：有些问题存在算法，但其资源需求使大规模实例难以在实践中求解；而不可判定问题则根本不存在能够普遍适用且保证终止的求解方法。(ocw.mit.edu)