考频地图
本章只出 1 道左右选择题,几乎都是时间复杂度分析。但“复杂度”这把尺子贯穿整门课:每学一个结构、一个算法,都要能说出它的时间和空间代价。
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 逻辑结构与存储结构 | ★★☆☆☆ | “下列属于逻辑结构 / 存储结构的是” |
| 算法的特性 | ★☆☆☆☆ | “算法的五个特性” |
| 时间复杂度 | ★★★★☆ | “下列程序段的时间复杂度是” |
| 空间复杂度 | ★★☆☆☆ | “原地工作是指” |
数据结构三要素
一、几个基本术语
| 术语 | 含义 | 例子(学生表) |
|---|---|---|
| 数据 | 所有能输入计算机并被处理的符号 | 整张学生表 |
| 数据元素 | 数据的基本单位,通常作为整体处理 | 一个学生的记录 |
| 数据项 | 构成数据元素的不可分割的最小单位 | 学号、姓名 |
| 数据对象 | 性质相同的数据元素的集合 | 所有学生 |
| 抽象数据类型 ADT | 数据对象 + 数据关系 + 基本操作,与实现无关 | “线性表”及其插入删除操作 |
二、逻辑结构:元素之间是什么关系
三、存储结构:在内存里怎么放
| 存储结构 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 顺序存储 | 逻辑相邻的元素物理位置也相邻 | 可随机存取,存储密度高 | 插入删除要移动元素;可能产生外部碎片 |
| 链式存储 | 用指针表示元素之间的关系 | 插入删除方便,不需连续空间 | 只能顺序存取;指针占额外空间 |
| 索引存储 | 另建索引表(关键字,地址) | 检索快 | 索引表占空间,增删要改索引 |
| 散列存储 | 由关键字直接算出存储地址 | 检索、增删都快 | 可能冲突,需处理冲突 |
- “有序表”“栈”“队列”“线性表”是逻辑结构;“顺序表”“链表”“散列表”“循环队列”是存储结构(或带存储的结构)。
- 同一逻辑结构可以有不同存储结构;存储结构影响运算的实现和效率,而运算的定义只依赖逻辑结构。
算法与复杂度
算法的五个特性:有穷性、确定性、可行性、输入(≥ 0 个)、输出(≥ 1 个)。好算法的目标:正确性、可读性、健壮性、高效率与低存储需求。注意“程序”可以不满足有穷性(如操作系统一直在运行),“算法”必须有穷。
一、时间复杂度:数基本操作执行几次
- 找到最深层循环里的语句(基本操作)。
- 设它执行 T(n) 次,列式子求和或解方程。
- 只保留最高阶项,去掉系数:T(n) = 3n² + 5n + 2 → O(n²)。
| n | log₂n | n log₂n | n² | 2ⁿ |
|---|---|---|---|---|
| 10 | 3.3 | 33 | 100 | 1024 |
| 100 | 6.6 | 664 | 10⁴ | ≈ 1.3×10³⁰ |
| 10⁶ | 20 | 2×10⁷ | 10¹² | 天文数字 |
二、五种典型代码,套路全在这里
i = 1; while (i <= n) i = i * 2; // 第 t 次后 i = 2ᵗ // 2ᵗ > n 时结束 → t = log₂n
x = 0; while (n >= (x+1)*(x+1)) x = x + 1; // 循环 t 次后 x = t,t² ≤ n → t ≈ √n
for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) x++; // 1 + 2 + … + n = n(n+1)/2
for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++) sum++; // 1 + 2 + 4 + … + 2ᵏ < 2n
求阶乘 fact(n) = n * fact(n-1):T(n) = T(n−1) + 1 → O(n)。
归并排序:T(n) = 2T(n/2) + n → 递归树每层总代价 n,共 log₂n 层 → O(n log n)。
斐波那契朴素递归:T(n) = T(n−1) + T(n−2) + 1 → O(2ⁿ)(指数级)。
三、最好、最坏、平均
同一算法对不同输入执行次数不同。例如在长度为 n 的数组中顺序查找:最好 1 次(第一个就是),最坏 n 次,等概率时平均 (n + 1)/2 次。不特别说明时,时间复杂度指最坏情况。
四、空间复杂度
算法运行所需的辅助空间(输入数据本身占用的不算)随 n 的增长。辅助空间为常数 O(1) 的算法称为原地工作。递归算法要算上递归栈:深度为 h 的递归至少需要 O(h) 空间(如快速排序平均 O(log n)、最坏 O(n))。
- O(log n) 的底数可以不写:log₂n 与 log₃n 只差一个常数倍。
- 两层循环不一定是 O(n²):要看内层次数是否与外层变量相关(如例 ④ 是 O(n))。
- “原地工作”不是“不需要辅助空间”,而是辅助空间为常量。
真题与自测
一、真题问法
问法:“下列程序段的时间复杂度是”——几乎每隔一年一道。做法:把循环变量第 t 次后的值写出来,令它到达边界,解出 t。
二、折叠自测
1. for(i=n; i>1; i=i/2) for(j=0;j<n;j++) x++; 的时间复杂度?
外层 log₂n 次,内层每次 n 次,O(n log n)。
2. i=0; s=0; while(s<n) {{ i++; s+=i; }} 的时间复杂度?
循环 t 次后 s = 1+2+…+t = t(t+1)/2 ≥ n 时结束,t ≈ √(2n),O(√n)。
3. 两个长度分别为 m、n 的升序链表合并为一个升序链表,最坏时间复杂度?
O(m + n),最坏比较 m + n − 1 次(常写作 O(max(m, n)))。
4. “算法的可行性”指什么?
算法中的操作都能通过已实现的基本运算执行有限次来完成。
5. 顺序存储和链式存储哪个支持随机存取?
顺序存储。给出下标即可由首地址直接算出元素地址。
三、考前速览
数据结构 = 逻辑 + 存储 + 运算。
复杂度只保留最高阶、去掉系数。
不说明时指最坏情况。
① 有序表是逻辑结构。
② 双重循环不一定 O(n²)。
③ 原地工作 = 辅助空间 O(1)。