数据结构与算法 / 系统课时
什么是算法
什么是算法
面对同一个问题,随手操作可能偶尔成功,算法则要求把求解过程写成可重复执行、能够判断正确与否的有限步骤。本课将用“寻找最大值”说明算法的定义、必要特征,以及它与普通操作说明的边界。
学习目标
- 能用自己的话说明算法的基本定义。
- 能识别输入、输出、步骤明确性、终止条件与基本操作。
- 能判断一段操作说明是否已经精确到算法层面。
算法解决的不是一次操作
算法是一组针对某类问题的明确规则:先规定允许的输入与正确输出。本课的例子要求对每个合法输入在有限步内返回正确答案。算法描述的是可复用的求解方法,而不是某个人在某次场景中的临时动作。
以“从一个非空整数序列中找出最大值”为例,可以把求解过程写成四步:
- 把第一个数记为当前最大值。
- 从第二个数开始逐个读取。
- 遇到更大的数就更新当前最大值。
- 扫描结束后输出当前最大值。
对任何有限非空整数序列,这个流程都按同一规则执行。读完前 k 个数时,当前最大值等于这 k 个数的最大值。初始 k=1 成立,下一步比较并取较大者保持性质。读完整个序列时该性质就是输出要求。若输入长度为 n,恰做 n−1 次大小比较。
一个合格算法的必要特征
- 输入:明确算法接受什么数据,以及数据需要满足哪些前置条件;某些算法也可以没有外部输入。
- 输出:至少产生一个可观察结果,结果形式和正确性要求必须能够说明。
- 步骤明确性要求每个动作和条件都可解释执行。确定性是指相同输入从相同初始状态出发走同样的路径。算法也可使用明确规定的随机选择,后续再区分其正确性和终止保证。
- 有限性:对合法输入,算法应在有限步骤后结束,而不是无限等待或无限循环。
- 有效性:每一步都能由计算机或执行者在有限时间内完成,不能依赖不可实现的操作。
算法与普通步骤的区别
| 对比项 | 普通操作说明 | 算法 |
|---|---|---|
| 目标 | 常面向一次具体任务 | 面向一类同结构问题 |
| 表达 | 可以依赖经验和语境 | 每一步都需要明确 |
| 结束条件 | 可能只说“做到合适为止” | 必须说明何时停止 |
| 结果验证 | 可能凭主观判断 | 能依据规则检查正确性 |
“把数值调整到合适大小”不是算法,因为“合适”没有可执行标准;改成“当数值大于 100 时每次减 10,直到不大于 100”后,执行条件、动作和停止条件都清楚,才具备算法形式。
如何判断一段说明是不是算法
检查时可以连续追问四个问题:输入范围是否清楚,每一步是否只有明确解释,所有合法输入是否都会结束,输出能否验证。任何一个问题没有答案,都说明描述还需要补充。
边界条件尤其重要。前面的算法要求序列有限且非空。若接口可能收到空序列,需要规定如何拒绝或返回特殊结果。如果要返回下标而最大值可能重复,还需明确返回第一个、最后一个或任意一个最大项。算法不仅要描述正常路径,也要说明允许输入的边界。
本课总结
- 算法是面向一类问题的有限、明确、可执行求解规则。
- 用前置条件、输出规格和终止理由检查过程是否完整,区分定义明确的随机动作与模糊动作。
- 普通步骤只有补齐条件、动作、停止方式和验证标准后,才可能成为算法。
下一课预告
下一课将区分算法与程序,说明同一算法如何用不同编程语言实现,以及为什么算法正确不等于程序一定正确。
按自己的节奏,确认真正理解。