第5章算法 · 计算机科学概论（第13版）教学页

LEARNING MAP

本章学习地图

六个小节回答六个问题；每节末尾有「本节小结」与课堂练习（共 12 题），参考答案在页面底部。

小节	核心问题	关键概念
5.1 算法的概念	什么样的步骤序列才配称为算法？	有序 · 无歧义 · 可执行 · 可终止
5.2 算法的表示	如何精确地把算法写下来给别人看？	原语 · 伪代码 · 函数与参数
5.3 算法的发现	算法是怎样被“想”出来的？	波利亚四阶段 · 逐步精化
5.4 迭代结构	如何用循环实现搜索与排序？	顺序搜索 · 循环控制 · 插入排序
5.5 递归结构	如何让函数调用自己来解题？	二分搜索 · 激活 · 递归控制
5.6 效率和正确性	算法有多快？如何确保它正确？	大Θ符号 · 断言 · 循环不变式

5.1 THE CONCEPT OF ALGORITHM

5.1 算法的概念

算法 algorithm：定义一个可终止过程的一组无歧义的、可执行的步骤的有序集合。

正式定义的四个关键词

Ordered

有序的 sequenced

各步骤按执行顺序有非常明确的结构。并行算法（parallel algorithm）是个例外：它包含多条步骤序列，执行流在不同处理器上分支再接合。

Unambiguous

无歧义的

每个步骤的含义唯一确定，不依赖解读者的猜测——科学必须建立在定义明确的术语（terminology）之上。

Executable

可执行的 effective

每个步骤都切实可行。计算机科学家用“有效的”（effective）一词来表示“可执行”。

Terminating

可终止的

算法的执行必须最终结束。永不停止的过程（如死循环）不满足算法定义。

非正式例子：烤蛋糕。“预热烤箱 → 混合原料 → 烘烤 40 分钟 → 取出冷却”有序、明确、可行且会结束——是算法；而“不断搅拌直到完美”既无明确终点又无法判定——不是算法。人脑中的许多活动（幻想、决策除外其创造性来源）都可看作算法执行的结果。

算法 · 程序 · 进程

Algorithm

算法

抽象的解决方法本身。算法是抽象的，与它的表示相区别：可用自然语言、流程图或程序设计语言表示，底层算法不变。

Program

程序

算法的表示（representation）：用程序设计语言把算法精确地写下来。

Process

进程

执行程序的活动（activity）：程序被机器运行时才真正“发生”。

类比：食谱、菜谱与下厨。做菜的方法 = 算法；写在纸上的菜谱 = 程序（中文、英文、图示皆可）；厨师真正下厨的过程 = 进程。方法不变，表示可变，每次执行各不相同。

本节小结 · 5.1

算法的正式定义：一组无歧义、可执行的步骤的有序集合，且定义的过程可终止——四个条件缺一不可。

算法是抽象的，与表示方式无关；程序是算法的表示，进程是执行算法的活动——算法把程序和进程联系在一起。

Q1算法的正式定义要求：算法是定义一个“____的过程”的一组无歧义的、可执行的步骤的有序集合。

A无限循环

B可终止

C并行执行

D人机交互

答案 B。算法定义的过程必须可终止（terminating）——永不结束的过程不是算法。并行只是步骤组织方式的一种变体。

Q2关于算法、程序、进程三者，下列说法正确的是？

A程序是执行算法的活动

B进程是算法的表示

C程序是算法的表示，进程是执行程序的活动

D三者是同一概念的不同译名

答案 C。程序是算法的表示（representation），进程是执行程序的活动（activity）——A、B 恰好说反了。

5.2 THE REPRESENTATION OF ALGORITHMS

5.2 算法的表示

用定义明确的构建块——原语（primitive）——来构造算法的表示，消除自然语言的歧义。

原语：语法与语义

Syntax

语法

原语的符号表示：它“长什么样”。例：单词 air 的语法由 a、i、r 三个符号按序组成。

Semantics

语义

原语的含义：它“指什么”。例：air 的语义是“一种充满整个世界的气体物质”。

程序设计语言（programming language）= 一组原语 + 说明如何组合这些原语来表达复杂想法的规则集合。机器指令是最低级的原语；高级语言的每个原语都是由低级原语构成的抽象工具，让算法可以在更高的概念层次上表达。

伪代码：三种基本结构

伪代码 pseudocode：算法开发中非正式表达想法的符号系统——比自然语言准确，比程序设计语言易读。

# 选择：闰年 if (年份是闰年): 每日总计 = 总数 / 366 else: 每日总计 = 总数 / 365 # 迭代：卖票 while (仍有票可卖): 卖票

选择用布尔条件二选一；迭代在条件为真时重复执行。

# 嵌套：缩进标明归属 if (未下雨): if (温度 == 热): 去游泳 else: 打高尔夫球 else: 看电视

缩进（indentation）告诉我们“温度是否为热”嵌套在外层 if 之内。

基础知识点：定序 sequence、选择 selection、迭代 iteration 是算法的构建块——每个算法都可以直接使用这三种结构来构造。赋值 name = expression 用来保存计算的值。

函数与参数：可复用的抽象工具

def greeting (): Count = 3 while (Count > 0): print the message "Hello" Count = Count - 1

用 Python 关键字 def 声明；名为 greeting 的函数打印 3 次 “Hello”。

if (...): ProcessLoan () else: RejectApplication () # 通用化：参数 def Sort (List):

每个函数本身就是一个算法——算法可以组合形成新算法。

Parameter

参数：让函数通用

不在函数内写死处理对象，而用类属名作参数，如 def Sort (List)；调用时传入“婚礼宾客列表”“组织成员列表”等具体列表。

Naming

命名约定

项名应是连续文本块：Pascal 大小写（EstimatedArrivalTime）或下划线（estimated_arrival_time）——本书倾向 Pascal 大小写。

本节小结 · 5.2

原语 = 语法（符号表示）+ 语义（含义）；程序设计语言 = 原语集合 + 组合规则。

伪代码三种结构：赋值、选择 if-else、迭代 while；冒号与缩进限定子结构边界。

函数 + 参数让算法成为可复用的抽象工具；算法可以组合形成新算法。

Q3原语的“语义”（semantics）指的是？

A原语的符号表示

B原语的执行速度

C原语的含义

D原语的拼写规则

答案 C。语义是原语的含义；“符号表示”是语法（syntax）——两者共同消除歧义。

Q4定序、选择和____是算法的构建块，每个算法都可以用它们来构造。

A迭代

B递归

C编译

D抽象

答案 A。定序、选择、迭代三种结构足以构造任何算法；递归本质上是迭代的另一种实现（5.5 节）。

5.3 ALGORITHM DISCOVERY

5.3 算法的发现

程序开发 = 发现潜在的算法 + 以程序方式表示算法——“发现”往往是更具挑战性的一步。

波利亚的问题求解四阶段

PHASE 1

理解问题

弄清已知、未知与目标——方向错了，后面越努力越偏。

PHASE 2

设计计划

设计一个解决问题的计划：找出已知与未知的联系。

PHASE 3

完成计划

执行计划，并检查每一步是否正确。

PHASE 4

评估与推广

评估准确度，以及它作为解决其他问题工具的潜力。

波利亚（G. Pólya，1887–1985），匈牙利裔数学家，1945 年在《如何解题》（How to Solve It）中提出这四个阶段。注意：它们不是必须按顺序遵循的步骤——仅“遵循”不能解决问题，解决问题必须有主动的开创精神；但回头总结时，往往会发现自己确实经历了这些阶段。

孵化期（incubation period）：苦思无果时去做别的事，答案有时会突然浮现——大脑的潜意识仿佛一直在思考，成功后把解决方案推给显意识。有意识地求解与突然灵感之间的这段时间，称为孵化期。

迈出第一步的三种方法

Work Backwards

反向解决问题

若问题是“从给定输入产生特定输出”，可从输出出发，反向推导出给定输入。

5.4 迭代结构

迭代结构 iterative structure：一组指令以循环（loop）方式重复执行，重复执行的指令组称为循环体（body）。

顺序搜索算法

def Search(List, TargetValue): if (List为空): 声明搜索失败 else: 选择List中的第一个条目作为TestEntry while (TargetValue大于TestEntry and 还有条目): 选择List中的下一个条目作为TestEntry if (TargetValue = TestEntry): 声明搜索成功 else: 声明搜索失败

顺序搜索（sequential search）按条目出现顺序逐项比对，又称线性搜索（linear search）。简单，适合短列表；对长列表则不如其他技术高效。

循环控制：初始化 · 测试 · 修改

活动	职责
初始化 initialization	建立初始状态，该状态会朝着终止条件被修改
测试 test	比较当前状态与终止条件，若相等则终止重复
修改 modification	改变状态，使之移向终止条件

终止条件（termination condition）是 while 中给出的条件的对立条件。初始化与修改必须保证它最终出现——设计循环时务必反复确认这一点，否则最简单的情形也会出错。

反例（死循环）：Number = 1; while (Number != 6): Number = Number + 2 —— Number 依次为 1、3、5、7、9……永远不等于 6，初始化与修改没有通向终止条件，循环无法终止。

for 循环：更高一级的抽象。for Item in List: … 隐式完成初始化、测试与修改，到达列表末尾自动终止（其他语言中常称 for-each）。最适合“对列表每个元素做同样的事”，不必单独跟踪循环计数变量。

插入排序算法

def Sort(List): N = 2 while (N 的值没有超过 List 的长度): 选择 List 中的第 N 个条目作为主元 pivot 把主元移到临时位置，留出一个空缺 while (空缺上方还有名字 and 该名字比主元大): 将空缺上方的名字下移到空缺将主元移到空缺上 N = N + 1

动画演示：插入排序（Fred, Alex, Diana, Byron, Carol）

蓝色 = 已排好序的前缀；橙色 = 当前主元（pivot）。点击“下一步”观察每个主元如何找到自己的家。

初始列表。排序目标：在列表自身内部完成，只移动条目，不占用额外空间。

嵌套循环：外层 while 控制主元位置（N 从 2 开始），内层 while 把比主元大的名字逐个下移腾位。外层循环体每执行一次，内层循环体被初始化并重复执行直到达到自己的终止条件。

本节小结 · 5.4

循环控制 = 初始化 + 测试 + 修改，三者必须保证终止条件最终出现，否则死循环。

顺序搜索逐个比对（线性搜索），适合短列表；for 循环是遍历列表的高级抽象。

插入排序反复把主元插入已排好序的前缀，是嵌套循环的典型例子。

Q7顺序搜索算法因为按条目出现顺序查找，又被称为？

A二分搜索

B哈希搜索

C线性搜索

D索引搜索

答案 C。顺序搜索 sequential search 又称线性搜索 linear search。

Q8循环控制由初始化、测试和____三个活动组成。

A编译

B声明

C输出

D修改

答案 D。初始化建立初始状态，测试比较终止条件，修改使状态移向终止条件——三者共同保证循环最终终止。

5.5 RECURSIVE STRUCTURES

5.5 递归结构

递归 recursion：函数直接或间接地调用自身——把问题分解为更小的同类子问题，直到最简单情形时停止并返回结果。

二分搜索算法

def Search(List, TargetValue): if (List为空): 报告搜索失败 else: TestEntry = List的中间条目 if (TargetValue == TestEntry): 报告搜索成功 if (TargetValue < TestEntry): Search(TestEntry前面的List部分, TargetValue) if (TargetValue > TestEntry): Search(TestEntry后面的List部分, TargetValue)

动画演示：在 15 个名字的有序列表中二分查找 “John”

灰色 = 已被排除；蓝色 = 当前比较的中间条目；绿色 = 命中。每一步搜索范围减半。

准备就绪：目标值 John。函数体内包含对自身的引用——把用在原始列表上的过程，应用到更小的列表上。

一分为二 → 二分搜索（binary search）。前提：列表必须已排好序——顺序一旦打乱，二分查找就失去依据。

递归控制：激活与三要素

Activation

激活：多个“副本”的错觉

执行递归函数时仿佛存在多个副本，每个副本称作一次激活（activation）。激活随算法前进而动态创建、最终消失；任何时刻只有一次激活在活跃执行，其余激活都在等待下一次激活终止后才能继续。

要素	在二分搜索中的体现
初始化	隐式开始：直接给出原始列表和目标值
修改	把任务修改为在更小的列表中搜索
终止条件	找到目标值，或任务缩小到搜索空列表

Loop vs Recursion

循环重复 vs 递归重复

顺序搜索以循环方式重复执行过程；二分搜索把每一阶段的重复当作前一阶段的子任务——实现“重复”的两条路径。

Implicit / Explicit

隐式与显式

递归的初始化常隐式地由参数传入（implicit），不像循环那样写在外部（explicit）——读递归代码时要在心里补出它。

本节小结 · 5.5

递归：函数调用自身，把问题分解为更小的同类子问题，直到最简单情形；每次调用产生一次“激活”。

二分搜索每次比较中间条目、排除一半，前提是列表有序。

递归控制与循环控制同样需要初始化、修改和终止条件，缺一不可。

Q9二分搜索算法能够正确工作的前提是？

A列表足够短

B列表已经排好序

C列表中没有重复项

D列表只能包含数字

答案 B。比较中间条目后之所以能断定该去哪一半，靠的正是列表的有序性。

Q10执行递归函数时，函数仿佛存在多个副本，每个副本称作函数的一次？

A迭代

B线程

C激活

D中断

答案 C。每次递归调用产生一次激活（activation）；任一时刻只有一次激活在活跃执行。

5.6 EFFICIENCY AND CORRECTNESS

5.6 效率和正确性

效率 efficiency：资源的利用程度——高效与低效算法之差，往往是“实用解决方案”与“不实用解决方案”之别。

算法效率与大Θ符号

算法	时间-输入图的形状	大Θ分类	输入规模翻倍时
插入排序 insertion sort	抛物线（二次表达式）	Θ(n²)	耗时约变为 4 倍
二分搜索 binary search	对数曲线（对数表达式）	Θ(log₂n)	只多一次比较

Big-Theta Notation

大Θ符号

图的大体形状由表达式的类型（而非具体表达式）决定：线性 → 直线，二次 → 抛物线，对数 → 对数曲线。习惯上用能产生该形状的最简单表达式标识它，通常基于最差情况分析。

Why It Matters

分类的意义

知道算法属于哪一类，就能预测它在更大输入下的性能，并与解决同一问题的其他算法公平比较——同一问题的不同正确算法，效率可能天差地别。

基础知识点：找到问题的高效算法，可以帮助我们解决该问题的更大实例；确定算法的效率，是通过对算法的形式化或数学推理来完成的。Θ(n²) 读作“n 的平方的大Θ”，Θ(log₂n) 读作“log₂n 的大Θ”。

软件验证：用形式逻辑证明正确

Precondition

前置条件

证明的起点：假设程序开始执行时满足的条件，如“输入确实是一个名字列表”。

Assertion

断言

建立在程序各个点上的语句：前置条件沿指令逐点传播的结果。例：进入 if 分支前，前置条件与测试条件皆真。

Postcondition

后置条件

期望的输出规格说明。若程序末尾建立的断言能推出后置条件，程序即被证明正确。

Loop Invariant

循环不变式

循环中每次进行终止测试时都成立的断言。循环终止后，循环不变式 + 终止条件 ⇒ 期望的后置条件。

证明链条：前置条件 →（沿指令逐点传播）→ 各处断言 → 末尾断言 ⇒ 后置条件。把验证简化为形式过程，可以防止与直觉有关的不准确结论。正确性靠形式化推理确定，而不是靠测试——测试只能发现错误的存在，不能证明没有错误。

本节小结 · 5.6

大Θ符号按增长曲线的形状分类算法：插入排序 Θ(n²)，二分搜索 Θ(log₂n)；高效算法让更大规模的实例可解。

正确性用前置条件、断言、后置条件与循环不变式作形式化证明，而非依赖测试；软件验证仍是活跃的研究领域。

Q11按最差情况分析，插入排序属于哪一类算法？

AΘ(log₂n)

BΘ(n)

CΘ(n²)

DΘ(1)

答案 C。插入排序嵌套循环，最差情况图呈抛物线 → Θ(n²)；对数曲线 Θ(log₂n) 是二分搜索。

Q12软件验证中，程序开始执行时所满足的条件称为？

A后置条件

B循环不变式

C断言

D前置条件

答案 D。开始时满足的是前置条件（precondition）；末尾要推出的是后置条件（postcondition）。

ANSWER KEY

课堂练习参考答案（共 12 题）

逐题一句话解析；错题请回到对应小节复习。

小节	题号	答案	一句话解析
5.1	Q1	B	算法必须定义一个可终止的过程——永不结束的过程不是算法。
5.1	Q2	C	程序是算法的表示，进程是执行程序（算法）的活动。
5.2	Q3	C	语义 = 含义；符号表示是“语法”。
5.2	Q4	A	定序、选择、迭代三种构建块即可构造任何算法。
5.3	Q5	B	先理解问题，再谈设计计划。
5.3	Q6	A	逐步精化从一般到特殊，是自顶向下方法。
5.4	Q7	C	顺序搜索又称线性搜索，按出现顺序逐项比对。
5.4	Q8	D	初始化、测试、修改——三者共同保证终止条件出现。
5.5	Q9	B	二分搜索依赖有序性：比较中间项后知道该去哪一半。
5.5	Q10	C	递归函数的每个“副本”是一次激活，任一时刻只有一个活跃。
5.6	Q11	C	插入排序最差情况图呈抛物线 → Θ(n²)。
5.6	Q12	D	开始时满足的是前置条件；末尾要推出的是后置条件。

速记：5.1 → B C ｜ 5.2 → C A ｜ 5.3 → B A ｜ 5.4 → C D ｜ 5.5 → B C ｜ 5.6 → C D

易错点提醒：① “程序”与“进程”别互换——表示 vs 活动；② 语法管“长相”，语义管“含义”；③ 二分搜索必须有序；④ 大Θ分类看曲线形状，不看具体表达式。

GLOSSARY

本章术语表（中英对照）

重点名词双语对照 + 一句话释义；建议结课时自查一遍。

术语	English	释义
算法	algorithm	可终止的精确步骤集合
并行算法	parallel algorithm	多执行流分支再接合
程序	program	算法的表示
进程	process	执行程序的活动
原语	primitive	定义明确的构建块
语法	syntax	原语的符号表示
语义	semantics	原语的含义
程序设计语言	programming language	原语集合 + 组合规则
伪代码	pseudocode	非正式的算法表达法
赋值语句	assignment statement	name = expression
迭代	iteration	重复执行直到满足条件
函数	function	命名的代码块（def）
参数	parameter	函数的类属名输入

术语	English	释义
逐步精化	stepwise refinement	逐级分解为子问题
自顶向下	top-down methodology	从一般到特殊
自底向上	bottom-up methodology	从特殊到一般
循环	loop	迭代结构，重复循环体
终止条件	termination condition	使循环停止的条件
顺序搜索	sequential search	逐项查找（线性搜索）
插入排序	insertion sort	把主元插入已排序前缀
主元	pivot	被移动的基准条目
递归	recursion	函数调用自身
二分搜索	binary search	有序列表逐次减半
激活	activation	递归函数的一次“副本”
大Θ符号	big-theta notation	按效率曲线形状分类
循环不变式	loop invariant	每次终止测试都成立的断言