数据结构与算法 / 系统课时

什么是算法

什么是算法

面对同一个问题,随手操作可能偶尔成功,算法则要求把求解过程写成可重复执行、能够判断正确与否的有限步骤。本课将用“寻找最大值”说明算法的定义、必要特征,以及它与普通操作说明的边界。

学习目标

  • 能用自己的话说明算法的基本定义。
  • 能识别输入、输出、步骤明确性、终止条件与基本操作。
  • 能判断一段操作说明是否已经精确到算法层面。

算法解决的不是一次操作

算法是一组针对某类问题的明确规则:先规定允许的输入与正确输出。本课的例子要求对每个合法输入在有限步内返回正确答案。算法描述的是可复用的求解方法,而不是某个人在某次场景中的临时动作。

以“从一个非空整数序列中找出最大值”为例,可以把求解过程写成四步:

  1. 把第一个数记为当前最大值。
  2. 从第二个数开始逐个读取。
  3. 遇到更大的数就更新当前最大值。
  4. 扫描结束后输出当前最大值。

对任何有限非空整数序列,这个流程都按同一规则执行。读完前 k 个数时,当前最大值等于这 k 个数的最大值。初始 k=1 成立,下一步比较并取较大者保持性质。读完整个序列时该性质就是输出要求。若输入长度为 n,恰做 n−1 次大小比较。

一个合格算法的必要特征

  • 输入:明确算法接受什么数据,以及数据需要满足哪些前置条件;某些算法也可以没有外部输入。
  • 输出:至少产生一个可观察结果,结果形式和正确性要求必须能够说明。
  • 步骤明确性要求每个动作和条件都可解释执行。确定性是指相同输入从相同初始状态出发走同样的路径。算法也可使用明确规定的随机选择,后续再区分其正确性和终止保证。
  • 有限性:对合法输入,算法应在有限步骤后结束,而不是无限等待或无限循环。
  • 有效性:每一步都能由计算机或执行者在有限时间内完成,不能依赖不可实现的操作。

算法与普通步骤的区别

对比项 普通操作说明 算法
目标 常面向一次具体任务 面向一类同结构问题
表达 可以依赖经验和语境 每一步都需要明确
结束条件 可能只说“做到合适为止” 必须说明何时停止
结果验证 可能凭主观判断 能依据规则检查正确性

“把数值调整到合适大小”不是算法,因为“合适”没有可执行标准;改成“当数值大于 100 时每次减 10,直到不大于 100”后,执行条件、动作和停止条件都清楚,才具备算法形式。

如何判断一段说明是不是算法

检查时可以连续追问四个问题:输入范围是否清楚,每一步是否只有明确解释,所有合法输入是否都会结束,输出能否验证。任何一个问题没有答案,都说明描述还需要补充。

边界条件尤其重要。前面的算法要求序列有限且非空。若接口可能收到空序列,需要规定如何拒绝或返回特殊结果。如果要返回下标而最大值可能重复,还需明确返回第一个、最后一个或任意一个最大项。算法不仅要描述正常路径,也要说明允许输入的边界。

本课总结

  • 算法是面向一类问题的有限、明确、可执行求解规则。
  • 用前置条件、输出规格和终止理由检查过程是否完整,区分定义明确的随机动作与模糊动作。
  • 普通步骤只有补齐条件、动作、停止方式和验证标准后,才可能成为算法。

下一课预告

下一课将区分算法与程序,说明同一算法如何用不同编程语言实现,以及为什么算法正确不等于程序一定正确。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

什么是算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通