4.1 算法及其特征
知识点
1.本单元的知识地图
| 小节 | 核心内容 | 对应问题类型 |
|---|---|---|
| 4.1 算法及其特征 | 算法是什么、怎么描述、怎么评价 | 打地基（概念与标准） |
| 4.2 数值计算 | 解析法、迭代法、递推、递归、穷举 | 算数（求根、求和、求 π） |
| 4.3 非数值计算 | 查找、排序、字符串处理 | 不算数（找东西、排队、比对） |
| 4.4 综合问题的解决 | 完整流程、模块化、测试与优化 | 做项目 |
一句话：4.1 讲"好算法的标准"，4.2／4.3 讲"常见算法套路"，4.4 讲"怎么把它们组装起来解决真问题"。
2.算法的定义
定义：算法是为解决某一特定问题而设计的一系列明确的、有限的操作步骤。
三层理解：
- 算法是方法，不是代码——同一算法可以用不同语言实现；
- 算法必须可执行——每一步都能真正做出来；
- 算法必须有结果——最终要解决问题。
算法与程序的区别（常考）：
| 对比 | 算法 | 程序 |
|---|---|---|
| 本质 | 解决问题的思路与步骤（逻辑） | 算法的具体实现（代码） |
| 形式 | 自然语言、流程图、伪代码 | 某种程序设计语言 |
| 依存 | 与语言无关 | 依赖具体语言与运行环境 |
| 能否运行 | 不能直接运行 | 能运行 |
关系式：程序 = 数据结构 + 算法（N. Wirth）。算法是程序的灵魂，数据结构是程序的骨架。
一个生活化的算法：泡方便面——①烧水 ②撕开包装 ③放调料 ④倒水 ⑤盖盖等 3 分钟。步骤明确、可执行、能结束，就是算法。
3.算法的五个特征（必背，五个都要能举例）
| 特征 | 含义 | 反例（不是算法） |
|---|---|---|
| 有穷性 | 必须在执行有限步之后结束，且每一步都能在有限时间内完成 | "不断加 1，直到找到最大的整数"——永不结束 |
| 确定性 | 每一步的含义必须明确、无歧义，同样的输入必得同样的结果 | "把数据调整得差不多"——"差不多"不明确 |
| 可行性 | 每一步都能实际执行（有足够的资源与手段） | "用尺子量出地球到月球的精确距离"——不可行 |
| 输入 | 有 0 个或多个输入 | 求圆周率可以没有输入（用级数算） |
| 输出 | 至少有一个输出（结果） | 只计算不输出任何结果，不能算解决 |
| （补充）通用性 | 能解决一类问题，而不只是一个具体实例 | 只算 3+5 的程序没有通用性 |
记忆口诀："有穷、确定、可行、有入、有出"——"穷、确、可、入、出"。
最容易考的两个：
- 有穷性——不是"很快结束"，而是一定能结束；
- 确定性——不能有"视情况而定"这种模糊描述。
4.三种基本结构（结构化程序设计的基石）
| 结构 | 特征 | 流程图表现 | 对应语句 |
|---|---|---|---|
| 顺序结构 | 按书写顺序逐条执行 | 框自上而下一条线 | 赋值、输入、输出 |
| 选择（分支）结构 | 根据条件选择执行某一路 | 菱形判断框，分叉后汇合 | if / elif / else |
| 循环结构 | 重复执行某段语句 | 流程线回到前面（回路） | for / while |
重要结论（结构化定理）：任何复杂算法都可以只用这三种基本结构组合而成。所以写程序时避免随意跳转（如 goto），代码才清晰可维护。
三种结构的组合关系：顺序是基础，选择与循环内部都由顺序语句组成；选择与循环可以互相嵌套。
5.算法的四种描述方式
| 方式 | 优点 | 缺点 | 适用场合 |
|---|---|---|---|
| 自然语言 | 通俗、易理解，无需专门训练 | 易歧义、冗长、不便于交流细节 | 初步构思、口头说明 |
| 流程图 | 直观形象，结构一目了然 | 复杂算法图幅大、绘制费时 | 教学、方案说明、评审 |
| 伪代码 | 严谨且接近代码，便于转成程序 | 需约定规则，不能直接运行 | 算法设计与交流（教材、论文常用） |
| 程序设计语言 | 可直接运行验证 | 受语法细节约束，与语言绑定 | 最终实现 |
伪代码示例（求 1 到 n 的和）：
输入 n
sum ← 0
i ← 1
当 i ≤ n 时循环
sum ← sum + i
i ← i + 1
输出 sum
要点：伪代码用 ← 表示赋值、用"当……时"表示循环，不纠结分号括号，重在表达逻辑。
6.怎么评价一个算法（四个维度）
| 维度 | 关注点 | 说明 |
|---|---|---|
| 正确性 | 能否得到正确结果 | 至少要通过正常数据、边界数据、异常数据的测试 |
| 可读性 | 人是否容易看懂 | 命名规范、注释、结构清晰——程序是给人看的，顺便给机器执行 |
| 健壮性 | 遇到非法输入时能否妥善处理 | 输入 0 不崩溃、输入字母不报错而是提示 |
| 效率 | 时间与空间的消耗 | 用时间复杂度与空间复杂度衡量 |
优先级：先正确，再可读，再健壮，最后才是效率——不能为了快而牺牲正确性。
7.时间复杂度（本小节难点，但要会判断）
定义：时间复杂度描述算法执行时间随问题规模 n 增长的变化趋势，用大 O 记法表示（只保留最高阶项，忽略常数与低阶项）。
为什么忽略常数：n 很大时，3n² + 100n + 5 中 n² 起决定作用，写成 O(n²) 就够了。
常见复杂度从优到劣：
| 复杂度 | 名称 | 典型算法 | n = 1000 时的量级 |
|---|---|---|---|
| O(1) | 常数阶 | 按下标取数组元素、哈希查找 | 1 次 |
| O(log n) | 对数阶 | 二分查找 | 约 10 次 |
| O(n) | 线性阶 | 顺序查找、一次遍历求和 | 1000 次 |
| O(n log n) | 线性对数阶 | 快速排序、归并排序 | 约 10000 次 |
| O(n²) | 平方阶 | 冒泡／选择／插入排序、双重循环 | 100 万次 |
| O(2ⁿ) | 指数阶 | 递归求斐波那契（不优化） | 天文数字 |
怎么"数"出复杂度（实用方法）：
- 没有循环，只有几条顺序语句 → O(1)；
- 一层循环，循环 n 次 → O(n)；
- 两层嵌套循环，各 n 次 → O(n²)；
- 每次把范围减半（
n = n // 2） → O(log n)。
代码判断示例：
# ① O(1)
a = 3 + 5
# ② O(n)
for i in range(n):
print(i)
# ③ O(n²)
for i in range(n):
for j in range(n):
print(i, j)
# ④ O(log n)
i = n
while i > 1:
i = i // 2
直观感受：n = 100 万时，O(n) 约百万次运算（不到 1 秒），而 O(n²) 是一万亿次（几乎算不完）——这就是"算法优劣"的实际意义。
8.空间复杂度（了解）
定义：算法运行时临时占用存储空间随 n 增长的趋势。
典型情况：
- 原地算法：只用了几个变量 → O(1) 空间（如冒泡排序、就地反转）；
- 需要额外数组/列表存中间结果 → O(n) 空间（如归并排序）；
- 递归：每层调用都要保存现场 → 空间与递归深度成正比。
时空权衡：有时用空间换时间（如哈希表、缓存），有时用时间换空间（如压缩存储）。
9.算法思想与计算思维
| 计算思维要素 | 在算法中的体现 |
|---|---|
| 抽象 | 把实际问题抽象成输入、输出与数据模型 |
| 分解 | 大问题拆成小问题（自顶向下设计） |
| 模式识别 | 认出"这是求和模式""这是查找模式" |
| 算法设计 | 选择合适的策略（解析、迭代、穷举、分治） |
四种常见算法策略（本单元会逐个接触）：
| 策略 | 思路 | 典型问题 |
|---|---|---|
| 解析法 | 直接套用公式计算 | 圆面积、一元二次方程求根 |
| 迭代法 | 用旧值推出新值，反复逼近 | 求平方根、求 π、二分法求根 |
| 穷举法 | 列举所有可能逐个检验 | 百钱百鸡、水仙花数、密码破解 |
| 递归法 | 把问题化为同类的更小规模问题 | 阶乘、汉诺塔、斐波那契 |
10.速查表
| 序号 | 考点 | 结论 |
|---|---|---|
| 1 | 算法定义 | 解决问题的有限、明确的操作步骤 |
| 2 | 算法五特征 | 有穷性、确定性、可行性、输入、输出 |
| 3 | 输入的数量 | 0 个或多个 |
| 4 | 输出的数量 | 至少 1 个 |
| 5 | "算法必须有输入" | 错（可以无输入） |
| 6 | "算法必须有输出" | 对（至少一个） |
| 7 | 三种基本结构 | 顺序、选择、循环 |
| 8 | 判断框形状 | 菱形 |
| 9 | 循环的流程图特征 | 流程线回指 |
| 10 | 四种描述方式 | 自然语言、流程图、伪代码、程序语言 |
| 11 | 算法与程序的关系 | 算法与语言无关，程序是算法的实现 |
| 12 | 程序公式 | 程序 = 数据结构 + 算法 |
| 13 | 评价四维度 | 正确性、可读性、健壮性、效率 |
| 14 | 评价的优先顺序 | 正确 → 可读 → 健壮 → 效率 |
| 15 | 时间复杂度定义 | 时间随 n 增长的趋势 |
| 16 | 大 O 只保留 | 最高阶项（忽略常数与低阶） |
| 17 | O(1) | 无循环、按下标访问 |
| 18 | O(log n) | 每次范围减半（二分查找） |
| 19 | O(n) | 一层循环、顺序查找 |
| 20 | O(n²) | 两层嵌套循环、冒泡排序 |
| 21 | 复杂度优劣顺序 | O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) |
| 22 | 空间复杂度 | 临时存储随 n 的增长趋势 |
| 23 | 递归的空间 | 与递归深度成正比 |
| 24 | 算法策略四种 | 解析、迭代、穷举、递归 |
11.课堂提示（讲课参考）
- "算法"从生活讲起：让学生写"如何从家到学校"的步骤，再挑一个写得含糊的（"坐车去"）指出违反确定性，一个写"一直走直到到"的指出可能违反有穷性——五个特征在 10 分钟内自然引出。
- 同一算法三种描述对比：求 1~100 的和，先写自然语言，再画流程图，再写伪代码，最后写 Python，学生就理解"同一件事的不同表达层次"。
- 时间复杂度用"数循环"入门：先不背公式，让学生把四段代码的循环次数数出来，再引出 O(n)、O(n²)、O(log n)。
- O(n²) 的"威力"用数据说话：n=1000 时冒泡排序约 50 万次比较，n=10000 时约 5000 万次——"为什么排序算法很重要"就讲清了。
- 强调"程序是给人看的"：让学生读一段没有注释、变量名全是 a1/a2 的代码，体会可读性的价值。