408

数据结构

DS-01-02 算法基本概念（定义/特性/效率度量）

---

一、定位信息

项目	内容
所属圈层	核心层
前置知识回顾	需先掌握DS-01-01中数据结构的基本概念（逻辑结构、存储结构、数据运算），因为算法就是对数据结构施加的运算的具体实现
知识网络定位	本单元是连接"数据结构概念"与"算法效率分析"的桥梁。理解算法的定义和特性是后续学习各种具体算法（排序、查找、图算法等）的前提，而效率度量方法则直接通向DS-01-03的时间复杂度分析
考点热度等级	M级（中频常考）——算法特性常以选择题形式考查，效率度量概念为后续复杂度分析题的必备基础

热度说明：基于大纲权重与通用命题规律推测，待真题分析后校准。

---

二、知识点讲解

2.1 算法的定义

算法（Algorithm） 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

直观理解：算法就像一份"菜谱"——告诉你先做什么、再做什么、最后做什么，按步骤执行就能得到结果。算法作用于数据结构之上，是对数据运算的具体实现。

算法的严格定义需要满足以下前提：算法必须有输入（零个或多个）、输出（至少一个），并且必须在有限步骤内终止。

2.2 算法的五大特性

一个合格的算法必须同时满足以下五个特性，缺一不可：

特性	含义	通俗理解
有穷性	算法必须在执行有限步之后终止，且每步都在有限时间内完成	菜谱的步骤不能写"一直搅拌下去"
确定性	算法的每一条指令必须有确切的含义，相同的输入只能得到相同的输出	"加适量盐"不是确定的，"加5克盐"才是确定的
可行性	算法中描述的操作都可以通过已经实现的基本运算执行有限次来完成	菜谱里的每一步都是你能做到的
输入	一个算法有零个或多个输入	有的菜需要食材（有输入），有的什么都不需要（零输入）
输出	一个算法有一个或多个输出	做菜必须有成品（输出），不能做完什么都没有

关键区分：算法的五大特性是"必须满足"的条件，缺一就不是算法。例如，操作系统虽然在运行，但它不是一个"有穷"的过程，所以严格来说操作系统程序不是一个算法。

2.3 好算法的四个目标

在满足五大特性的前提下，一个"好"的算法还应该追求以下目标：

目标	含义	重要程度
正确性	算法能够正确地解决求解问题	最基本要求
可读性	算法容易被人理解	便于维护和调试
健壮性	对非法输入能做出适当反应，而非产生不可预料的结果	实际工程中极其重要
高效性（效率）	执行时间短、占用存储空间少	408考试重点考查

408考试重点：在考研中，"高效性"是最核心的考查点，具体体现为时间复杂度和空间复杂度的分析。

2.4 算法效率的度量方法

算法效率的度量主要有两种方法：

度量方法	做法	优缺点
事后统计法	编写程序运行，实际测量运行时间和占用空间	优点：真实。缺点：依赖硬件环境、需要编码实现、受输入数据影响大，不实用
事前分析估算法	在算法编写前，通过分析算法策略和问题规模来估算效率	优点：不依赖硬件、无需编码、通用性强。缺点：是估算值

408考试采用的是事前分析估算法，即通过数学方法分析算法的时间复杂度和空间复杂度。

2.5 影响算法效率的因素

在事前分析估算中，一个算法的执行时间主要受以下因素影响：

1. 算法策略本身：这是决定性因素。例如，折半查找比顺序查找快得多
2. 问题规模 $n$：输入数据量的大小。例如，对10个数排序和对100万个数排序，耗时差异巨大
3. 输入数据的具体状态：同一算法，不同输入可能导致执行时间不同（如快速排序在已排序数组上退化）
4. 编程语言与编译器：同一算法用不同语言实现，执行速度不同（但考研中不考虑此因素）
5. 硬件环境：CPU速度、内存大小等（考研中也不考虑此因素）

考研约定：在分析算法效率时，只关注算法策略和问题规模 $n$，将后三个因素排除在外。这正是大O记号的设计初衷。

2.6 从执行次数到时间复杂度

算法的执行时间可以表示为所有语句执行次数（频度）之和。设每条语句的执行次数为 $c_i$，语句条数为 $m$，则：

$T(n) = \sum_{i=1}^{m} c_i \cdot f_i(n)$

其中 $f_i(n)$ 是第 $i$ 条语句的频度（执行次数与问题规模 $n$ 的函数关系）。

当 $n \to \infty$ 时，$T(n)$ 的增长趋势由最高阶项决定，由此引入大O记号——详见DS-01-03。

---

三、记忆与理解辅助

技巧1：算法五大特性口诀

"有确可出入"——有穷性、确定性、可行性、输入、输出

或者更形象地记为：

"有（有穷）确（确定）可（可行）进（输入）出（输出）"，像进出一个有明确规则的房间。

技巧2：五大特性 vs 好算法四目标对比表

维度	五大特性	好算法四目标
性质	必须满足（缺一不可）	追求目标（越高越好）
不满足时	不是算法	仍然是算法，但质量差
具体内容	有穷性、确定性、可行性、输入、输出	正确性、可读性、健壮性、高效性
考查方式	选择题判断"哪个不是算法"	结合复杂度分析出综合题

技巧3：效率度量的方法选择

408考试只用事前分析估算法，不考虑硬件、语言、编译器差异。记住这个约定，考试时不要"较真"说"还要看硬件"。

技巧4：影响效率的因素排序

记住：算法策略 >> 问题规模 >> 输入状态。其中算法策略是决定性因素，问题规模是分析的核心变量，输入状态会影响最好/最坏情况。

---

四、例题与精解

例题1（基础）

题目：以下关于算法特性的叙述中，正确的是（　）。

A. 算法可以没有输出，但必须有输入 B. 算法的确定性是指算法的执行结果是唯一的 C. 算法的有穷性是指算法必须在执行有限步之后终止 D. 算法的可行性是指算法可以由人手工完成

命题意图：考查对算法五大特性定义的精确理解。

解答：

审题分析：需要逐项判断对算法特性的描述是否准确。

解题思路：将每个选项与算法特性的标准定义进行比对。

完整步骤：

• A项：算法必须有至少一个输出（可以没有输入，但不能没有输出）。例如，打印"Hello World"的程序就是一个零输入、有输出的算法。错误。

• B项：确定性是指每条指令有确切含义，相同的输入在相同条件下只能得到相同的输出。但"执行结果是唯一的"这种表述不够严谨——确定性强调的是指令的含义明确，而非结果唯一。此外，有些算法（如随机化算法）可能有多个输出，但408范围内确定性确实意味着结果唯一。此选项表述勉强可接受，但有更好的选项。

• C项：有穷性的定义确实是"算法必须在执行有限步之后终止，且每一步都在有限时间内完成"。正确。

• D项：可行性是指算法中的每一步操作都可以通过基本运算执行有限次来完成，强调的是计算机可执行，而非人手工完成。错误。

答案：C

方法反思：算法特性的辨析题是高频选择题，关键在于记住每个特性的标准定义，不要被似是而非的表述迷惑。特别注意"有穷性"和"可行性"的区别。

---

例题2（中等）

题目：分析以下算法，回答问题。

void fun(int n) {          // 输入：问题规模n
    int i = 1;              // 语句①：执行1次
    while (i <= n) {        // 语句②：执行？
        i = i * 2;          // 语句③：执行？
    }
}

（1）该算法是否满足算法的五大特性？逐一说明。 （2）语句②和语句③各执行了多少次？（用 $n$ 表示）

命题意图：综合考查算法特性的理解和基本的语句频度分析能力。

解答：

审题分析：第一问考查五大特性的判断；第二问需要分析循环的执行次数。

解题思路：第一问逐一核对五大特性；第二问追踪变量 $i$ 的变化规律。

完整步骤：

（1）五大特性检验：

特性	是否满足	说明
有穷性	✅	$i$ 每次翻倍，$i = 2^k$，当 $2^k > n$ 时循环终止，即 $k > \log_2 n$，最多执行 $\lfloor \log_2 n \rfloor + 1$ 次，有限步内终止
确定性	✅	每条指令含义明确，相同输入结果相同
可行性	✅	乘法和比较都是基本运算
输入	✅	有一个输入 $n$
输出	✅	函数执行完毕（隐式输出），虽无显式return，但函数调用本身产生副作用（修改了 $i$）

注意：严格来说，此函数没有显式输出，但在408的算法分析中，只要算法执行会产生可观察的效果（如修改全局变量、打印等），就视为有输出。

（2）语句频度分析：

设循环执行了 $k$ 次后终止，则 $i$ 的变化过程为：

$i: 1 \to 2 \to 4 \to 8 \to \cdots \to 2^k$

循环终止条件为 $i > n$，即 $2^k > n$，解得 $k > \log_2 n$。

• 语句②（while条件判断）：执行了 $k+1 = \lfloor \log_2 n \rfloor + 2$ 次（最后一次判断为假退出）
• 语句③（i = i * 2）：执行了 $k = \lfloor \log_2 n \rfloor + 1$ 次

方法反思：分析循环频度的关键是找到循环变量的变化规律。对于 i = i * 2 这类倍增型循环，执行次数与 $\log_2 n$ 相关；对于 i = i + 1 的普通循环，执行次数与 $n$ 相关。这是后续时间复杂度分析的基础。

---

五、考情分析

分析维度	说明
近5年考查频次	约2~3次，主要出现在选择题中
常见题型	选择题（概念辨析）、综合题的铺垫部分
分值占比	选择题2分；作为综合题基础时约占3~5分
命题趋势	单独考查算法特性的情况减少，更多与时间复杂度分析结合考查。近年趋势是给出一段代码，要求分析执行次数并判断复杂度

基于大纲与命题规律推测，待真题分析后校准。

---

六、易错点提醒

易错点1

• 错误表现：认为"算法可以没有输出"或"算法可以没有输入"
• 错误原因：对输入和输出的要求记忆不清
• 正确做法：算法可以没有输入（如求 $1+2+\cdots+100$），但必须有输出（否则算法没有意义）。五个特性中，输入可以为零个，输出至少一个

易错点2

• 错误表现：将操作系统、死循环程序视为算法
• 错误原因：忽略了有穷性要求
• 正确做法：算法必须在有限步内终止。操作系统是持续运行的程序，不满足有穷性，因此不是算法。但操作系统中使用的调度算法、页面置换算法等单个模块是算法

易错点3

• 错误表现：分析循环执行次数时，将 while 条件判断的次数漏算或多算一次
• 错误原因：没有区分"循环体执行次数"和"条件判断次数"
• 正确做法：while 循环的条件判断次数 = 循环体执行次数 + 1（最后一次判断为假退出）。例如，循环体执行3次，则条件判断了4次

易错点4

• 错误表现：认为"可行性"就是"人能手工完成"
• 错误原因：对可行性的定义理解偏差
• 正确做法：可行性是指算法中描述的操作可以通过已经实现的基本运算执行有限次来完成，强调的是计算机可执行，而非人工可完成

---

七、来源标注

• 依据2026考研统考大纲（408计算机学科专业基础综合·数据结构部分）
• 依据《数据结构（C语言版）》严蔚敏版第一章算法与算法分析
• 依据大学本科经典教材共识