跳转到内容

算法设计

来自VeritasWiki 真理百科

算法设计(Algorithm Design)是指针对特定问题,构造出明确、有限、可机械执行的操作步骤,并用合适的数据结构加以实现的过程。它是计算机科学的核心活动之一,也是把"问题"转化为"可被机器求解"的关键环节。[1]从工程角度看,算法本质上是根据问题需求,在数据的逻辑结构和存储结构基础上定义的一种运算规则;算法与数据结构互相依存、彼此支持,"数据结构 + 算法 = 程序"这一朴素等式,正说明了二者不可分割的关系。[2]

算法的历史脉络

算法的发展是一部跨越数千年的思想进化史,其核心是"解决问题的明确步骤"。早在公元前 300 年左右,欧几里得就提出了用于计算最大公约数的欧几里得算法,这是现存最古老的完整算法之一。[3]9 世纪,波斯数学家花拉子米在其著作中系统性地用步骤描述算术运算,其名字拉丁化后即为"算法"(Algorithm)一词的由来。[4]进入 20 世纪 30 至 40 年代,算法成为一门严格科学:1936 年图灵提出图灵机,精确定义了"可计算"的概念,为所有算法提供了理论模型和极限;同一时期丘奇用 λ 演算得出类似结论,丘奇-图灵论题奠定了现代计算机科学的理论基础;1945 年冯·诺依曼提出"存储程序"的计算机设计,使算法可以像数据一样被存储和执行。[5]20 世纪 50 至 70 年代,高德纳的《计算机程序设计艺术》首次系统地将算法分析作为一门科学来研究,大 O 记号被广泛用于量化算法效率,P 与 NP 问题于 1971 年由斯蒂芬·库克提出,成为计算机科学最著名的未解难题;快速排序、快速傅里叶变换、Dijkstra 最短路径等经典算法也在此期间涌现。

衡量算法的尺度:效率与复杂度

设计算法之后,必须对其好坏做出评判。可读性是一个重要标志,可读性不好不仅无助于理解算法,晦涩难懂的算法往往还隐含错误、不易调试。[6]健壮性要求算法在输入数据非法时做出恰当反应或处理,而不是莫名其妙地输出结果;高效率与低存储量则分别指算法的执行时间和最大存储空间需求,两者的复杂度都与问题规模有关。[7]算法分析的任务正是利用数学工具讨论其复杂度,探讨具体算法对问题的适应性。渐进记号把增长量级归入若干档:常数 O(1)、对数 O(log n)、线性 O(n)、线性对数 O(n log n)、平方 O(n²)、立方 O(n³),以及指数级 O(2ⁿ) 与阶乘级 O(n!);计算时先找出算法的基本操作,确定其执行次数,再取同数量级函数,低阶项与首项系数都被略去。[8]空间复杂度与之平行,衡量算法自身、输入输出以及运行中临时开辟的存储空间,同样以渐进形式表示;早期计算机时间与空间都极其珍贵,硬件进步缓解了存储压力,时间效率却未同步改善,因此时间复杂度始终是算法分析的关键。[9]

分治与动态规划:两种拆解方式

面对规模庞大的问题,最朴素的办法是穷举——把可能是解的候选解按顺序逐一枚举检验;它思路直接、适应性却差,规模稍大便会失效。分治法换了一条路:把原问题分解为若干规模更小、彼此独立、与原问题形式相同的子问题,分别求解后再合并结果。归并排序与快速排序是典型代表,前者把序列一分为二、排好再合并,无论数据如何分布都稳定保持在 O(n log n) 这一档。[10]

动态规划处理的是另一类结构。它的基本思想与分治类似,同样把问题分解为若干子问题并按顺序求解,前一子问题的解为后一子问题提供信息;区别在于,动态规划面对的问题通常具有重叠子问题,若直接递归会把同一件事反复计算,于是对每个子问题只求解一次,把不同阶段的不同状态存进表格,再次需要时直接查表。[11]能这样做的条件有三:最优子结构,即整体最优解所含子问题的解也最优;无后效性,即某阶段状态一旦确定便不受此后决策影响;以及子问题重叠。划分阶段、确定状态与状态变量、写出状态转移方程、寻找边界条件,构成了动态规划求解的标准动作。[12]与二者相比,贪心法每一步只取当前看来最好的选择,速度快却需要额外证明其正确性;回溯与分支限界则在解空间中系统搜索,靠剪枝把不可能的分支提前砍掉——选择哪种范式,取决于问题自身的结构,而非算法的"先进程度"。

经典设计策略

算法设计有一系列经典方法。迭代法用于求方程或方程组的近似根,通过不断用新近似值替换旧值,直至满足指定精度。[13]穷举搜索法对可能是解的众多候选解按顺序逐一枚举和检验,从中找出符合要求的候选解,优点是思路直接,缺点是程序通常难以适应变化的情况。[14]除此之外,分治法、动态规划、贪心法、回溯法和分支限界等也都是常用的设计范式。设计算法的一般过程可以归纳为若干步骤:通过对问题详细分析抽象出相应的数学模型;确定使用的数据结构并在此基础上设计操作算法;选用某种语言将算法转化成程序;最后调试并运行这些程序。[15]

从手工规则到机器学习范式

20 世纪 80 年代至今,算法渗透到社会各个角落并持续进化。传统算法以人编写的规则和明确步骤为主,而在大数据与机器学习时代,以数据驱动为核心的机器学习算法成为主流,实现了从"编程解决问题"到"从数据中学习规律"的范式转变。[16]典型的例子是遗传算法,它模仿自然选择的原理,把任一设计方案看作由无数片段构成的"遗传基因",通过随机改变某些片段或使其突变来改善整体设计,已在机器人运动、计算机安全、制药等领域得到应用。[17]与此同时,量子计算算法(如 Shor 算法)、生物计算算法等新模型不断涌现,算法的公平性、可解释性、隐私与伦理问题也成为社会关注的焦点。

评判一个好算法的标准

综合来看,一个好的算法设计需要在正确性、可读性、健壮性、时间和空间效率之间取得平衡。在满足以上基本品质之后,还可以进一步对算法进行优化,尽量满足时间效率高和空间存储量低的需求。[18]在编译原理、数据库原理、人工智能、算法设计与分析等后续课程中,算法设计都是贯穿始终的基础能力。从巴比伦人的步骤记录,到今天支撑人工智能大模型的海量并行计算,算法始终是将人类智慧转化为机器可执行指令的桥梁。

参考资料

  1. ↑ 智能计算、群智能、多目标优化、模糊控制之学习笔记,科学网,科学网。
  2. ↑ 智能计算、群智能、多目标优化、模糊控制之学习笔记,科学网,科学网。
  3. ↑ 算法简史!,科学网,科学网。
  4. ↑ 算法简史!,科学网,科学网。
  5. ↑ 算法简史!,科学网,科学网。
  6. ↑ 设计算法,科普中国,科普中国。
  7. ↑ 设计算法,科普中国,科普中国。
  8. ↑ [科普中国-时间复杂度],科普中国。
  9. ↑ [科普中国-算法复杂性],科普中国。
  10. ↑ [科普中国-时间复杂度],科普中国。
  11. ↑ [科普中国-动态规划算法],科普中国。
  12. ↑ [科普中国-动态规划算法],科普中国。
  13. ↑ 软件算法,科普中国,科普中国。
  14. ↑ 软件算法,科普中国,科普中国。
  15. ↑ 设计算法,科普中国,科普中国。
  16. ↑ 算法简史!,科学网,科学网。
  17. ↑ 遗传算法:让发明自动"进化",科学网,科学网。
  18. ↑ 设计算法,科普中国,科普中国。