首页/数据结构/第 1 章 绪论
408 计算机学科专业基础 数据结构 第 1 章

绪论
逻辑结构、存储结构与复杂度

本章约 1 道选择题,几乎都是时间复杂度分析。会“数循环次数”这一招就够了。

后面每一章都会反复用到两件事:这个结构在内存里怎么放(存储结构),以及这个操作要花多少时间、多少空间(复杂度)。先把这两把尺子磨好。

3 个考点模块 5 种复杂度套路 1 张图
log n n n² 2ⁿ n
00
复习策略

考频地图

★★☆☆☆ 低频 选择题

本章只出 1 道左右选择题,几乎都是时间复杂度分析。但“复杂度”这把尺子贯穿整门课:每学一个结构、一个算法,都要能说出它的时间和空间代价。

考点考频常见问法
逻辑结构与存储结构★★☆☆☆“下列属于逻辑结构 / 存储结构的是”
算法的特性★☆☆☆☆“算法的五个特性”
时间复杂度★★★★☆“下列程序段的时间复杂度是”
空间复杂度★★☆☆☆“原地工作是指”
一句话:数据结构 = 逻辑结构 + 存储结构 + 运算。时间复杂度只看“基本操作执行次数”随 n 增长的数量级:找出最内层语句,数它执行了多少次,保留最高阶、去掉系数。
01
1.1 · 打基础

数据结构三要素

★★☆☆☆ 低频 概念

一、几个基本术语

术语含义例子(学生表)
数据所有能输入计算机并被处理的符号整张学生表
数据元素数据的基本单位,通常作为整体处理一个学生的记录
数据项构成数据元素的不可分割的最小单位学号、姓名
数据对象性质相同的数据元素的集合所有学生
抽象数据类型 ADT数据对象 + 数据关系 + 基本操作,与实现无关“线性表”及其插入删除操作

二、逻辑结构:元素之间是什么关系

集合线性结构树形结构图状结构 只是同属一个集合一对一一对多多对多
图 1-1 四种基本逻辑结构。线性结构之外的三种统称非线性结构。

三、存储结构:在内存里怎么放

存储结构做法优点缺点
顺序存储逻辑相邻的元素物理位置也相邻可随机存取,存储密度高插入删除要移动元素;可能产生外部碎片
链式存储用指针表示元素之间的关系插入删除方便,不需连续空间只能顺序存取;指针占额外空间
索引存储另建索引表(关键字,地址)检索快索引表占空间,增删要改索引
散列存储由关键字直接算出存储地址检索、增删都快可能冲突,需处理冲突
  • “有序表”“栈”“队列”“线性表”是逻辑结构;“顺序表”“链表”“散列表”“循环队列”是存储结构(或带存储的结构)。
  • 同一逻辑结构可以有不同存储结构;存储结构影响运算的实现和效率,而运算的定义只依赖逻辑结构。
02
1.2 · 必考

算法与复杂度

★★★★☆ 高频 选择题

算法的五个特性:有穷性、确定性、可行性、输入(≥ 0 个)、输出(≥ 1 个)。好算法的目标:正确性、可读性、健壮性、高效率与低存储需求。注意“程序”可以不满足有穷性(如操作系统一直在运行),“算法”必须有穷。

一、时间复杂度:数基本操作执行几次

  1. 找到最深层循环里的语句(基本操作)。
  2. 设它执行 T(n) 次,列式子求和或解方程。
  3. 只保留最高阶项,去掉系数:T(n) = 3n² + 5n + 2 → O(n²)。
常见阶从小到大(必背): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
nlog₂nn log₂nn²2ⁿ
103.3331001024
1006.666410⁴≈ 1.3×10³⁰
10⁶202×10⁷10¹²天文数字

二、五种典型代码,套路全在这里

① 乘法递增:O(log n)
i = 1;
while (i <= n)
    i = i * 2;   // 第 t 次后 i = 2ᵗ
// 2ᵗ > n 时结束 → t = log₂n
② 平方根:O(√n)(2012 真题)
x = 0;
while (n >= (x+1)*(x+1))
    x = x + 1;
// 循环 t 次后 x = t,t² ≤ n → t ≈ √n
③ 依赖外层的双重循环:O(n²)
for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        x++;
// 1 + 2 + … + n = n(n+1)/2
④ 外层倍增、内层到 i:O(n)(2017 真题)
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))。
  • “原地工作”不是“不需要辅助空间”,而是辅助空间为常量。
03
实战

真题与自测

★★★☆☆ 收口 选择题

一、真题问法

问法:“下列程序段的时间复杂度是”——几乎每隔一年一道。做法:把循环变量第 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. 顺序存储和链式存储哪个支持随机存取?

顺序存储。给出下标即可由首地址直接算出元素地址。

三、考前速览

3 句话

数据结构 = 逻辑 + 存储 + 运算。
复杂度只保留最高阶、去掉系数。
不说明时指最坏情况。

3 个易错

① 有序表是逻辑结构。
② 双重循环不一定 O(n²)。
③ 原地工作 = 辅助空间 O(1)。