数据结构第一章复习：基本概念与算法复杂度分析

一、为什么第一章非常重要

很多同学一开始学数据结构，会觉得第一章都是“定义题”，背一背就行。其实不是。

第一章决定了你后面学线性表、栈、队列、树、图时，脑子里有没有一个统一框架。
你后面学的所有结构，本质上都在回答这几件事：

数据之间是什么关系 —— 这叫逻辑结构。
这种关系在计算机里怎么存 —— 这叫存储结构。
我要对这些数据做什么操作 —— 这叫运算。
这些操作写成算法后，效率怎么样 —— 这就进入复杂度分析。

所以，第一章其实是整本书的“世界观”。

二、先把最基础的几个概念分清

在这里插入图片描述

1. 数据（Data）

数据是对客观事物的符号表示，是计算机中可以输入、处理、存储和输出的对象。
它不只是数字，也包括字符、图像、声音、状态等。

你可以把“数据”理解成：进入计算机世界的一切可表示对象。

2. 数据元素（Data Element）

数据元素是数据的基本单位，通常是程序中作为一个整体进行考虑和处理的对象。

例如，在学生信息管理系统中：

一个学生记录可以看成一个数据元素；
一本书的信息可以看成一个数据元素；
一个用户账号也可以看成一个数据元素。

所以，数据元素强调的是“作为整体被处理”。

3. 数据项（Data Item）

数据项是构成数据元素的不可分割的最小单位。

继续用“学生记录”举例：

学号
姓名
性别
年龄

这些字段就是数据项。
也就是说：

数据项 < 数据元素 < 数据对象

4. 数据对象（Data Object）

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

比如：

所有学生记录组成一个数据对象；
所有整数构成一个数据对象；
一组图书记录也可以构成一个数据对象。

它更强调“同类元素的集合”。

5. 数据类型（Data Type）

数据类型可以理解为：

一组值的集合 + 定义在该集合上的一组操作

例如：

int：取值是整数，支持加减乘除、比较等运算；
char：取值是字符，支持字符相关处理；
自定义结构体类型：取值是一类复合对象，支持相应操作。

从复习角度看，数据类型关注的是：
“能存什么值”和“能做什么操作”。

6. 数据结构（Data Structure）

这是全章最核心的概念。

数据结构不是单纯“很多数据放在一起”，而是：

相互之间存在一种或多种特定关系的数据元素的集合。

所以，数据结构至少包含两层意思：

有数据元素；
元素之间有关系。

比如：

线性表中，元素是一对一的前后关系；
树中，元素是一对多的层次关系；
图中，元素之间可以是多对多关系。

一句话总结：

数据结构 = 数据元素 + 关系

三、数据结构的三要素

在这里插入图片描述

教材通常把数据结构分成三部分来理解：

逻辑结构
存储结构（物理结构）
数据的运算

这三者一定要连起来看。

1. 逻辑结构：先看“关系是什么”

逻辑结构描述的是数据元素之间的逻辑关系，和它们在内存里怎么摆放没有直接关系。

常见逻辑结构有四类：

（1）集合结构

集合中的元素除了“同属于一个集合”外，彼此没有其他关系。

例如：

一组学生
一组整数
一组商品

集合结构强调“有共同属性，但无特定次序关系”。

（2）线性结构

线性结构中的元素之间存在一对一关系，除首尾外，每个元素通常只有一个直接前驱和一个直接后继。

典型例子：

数组
线性表
栈
队列
字符串

看到“排成一条线”“前后相邻”，通常就是线性结构。

（3）树形结构

树形结构中的元素之间存在一对多关系，体现层次性。

典型例子：

文件目录
组织架构
二叉树
堆

你可以把树理解成“有根、有层级、有父子关系”的结构。

（4）图状结构或网状结构

图结构中的元素之间存在多对多关系。

典型例子：

社交网络
地图交通网络
网页链接关系
课程先修关系（某些情况下也可表示为图）

图比树更一般，因为一个结点可以与多个结点发生复杂连接。

2. 存储结构：再看“在计算机里怎么存”

在这里插入图片描述

存储结构，也叫物理结构，是逻辑结构在计算机中的表示方式。
同一种逻辑结构，可以有不同的存储方式。

常见存储结构有四种：

（1）顺序存储

把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。

典型代表：数组。

特点：

支持随机访问；
查找某个位置的元素很快；
但插入、删除可能要移动大量元素。

一句话记忆：
顺序存储访问快，插删可能慢。

（2）链式存储

元素不要求物理上连续，而是通过指针（或引用）表示逻辑关系。

典型代表：链表。

特点：

插入、删除灵活；
不要求连续空间；
但访问某个中间位置时通常不能直接跳过去，需要沿链逐个找。

一句话记忆：
链式存储插删方便，定位不如顺序快。

（3）索引存储

除了存放数据本身，还额外建立索引表，用来提高查找效率。

你可以把它类比为：

书的目录
数据库中的索引
稀疏矩阵中的某些辅助结构

特点：

查找效率高；
但需要额外索引空间。

（4）散列存储（哈希存储）

根据关键字直接计算存储地址。

特点：

理想情况下查找非常快；
但可能出现冲突，需要设计冲突处理方法。

一句话记忆：
哈希本质上是“用计算换查找速度”。

3. 数据的运算：最后看“你要对它做什么”

任何一种数据结构，最终都不是为了“摆着好看”，而是为了支持运算。

常见运算包括：

插入
删除
查找
修改
遍历
排序
合并
分解

所以从更抽象的角度看，学习一种数据结构，本质上是在学：

它支持哪些操作，以及这些操作代价如何。

4. 抽象数据类型（ADT）是什么

抽象数据类型强调的是：

数据对象是什么；
可以进行哪些操作；
不关心底层具体如何实现。

例如“栈”这个概念：

逻辑上它是后进先出（LIFO）；
操作上它支持 push、pop、top；
至于底层是用数组实现还是链表实现，不属于 ADT 的核心定义。

这点特别重要，因为它体现了：

逻辑与实现分离

这也是计算机科学中非常重要的思想。

四、算法的基本概念：算法不只是“代码”

1. 什么是算法

算法是为了解决某个问题而给出的有限指令序列。

这里有两个关键词：

解决问题
有限步骤

所以，并不是一段代码就一定是好算法；
算法必须围绕问题目标，并且步骤明确、有限、可执行。

2. 一个算法通常具备五个特性

（1）有穷性

算法必须在有限步之内结束，不能无限执行下去。

（2）确定性

算法中的每一步都必须有明确含义，不能模棱两可。

例如“找一个差不多大的数”就不是严格算法表达；
而“从左到右依次比较”就是明确的。

（3）可行性

算法中的每一步都必须是可以通过已有基本运算在有限时间内完成的。

也就是说，算法不能包含无法执行的“理想动作”。

（4）输入

一个算法可以有零个、一个或多个输入。

（5）输出

一个算法至少要有一个输出。
输出是算法解决问题后的结果体现。

3. 怎样评价一个“好算法”

教材通常提到以下几个标准：

正确性

算法首先必须把问题解决对。
效率再高，结果错了也没有意义。

可读性

算法应当易于理解、易于交流，也利于调试和维护。

健壮性

对非法输入、异常情况有合理处理能力，而不是直接崩溃。

高效率与低存储量需求

也就是我们常说的：

时间代价尽量低
空间代价尽量少

所以评价算法，不能只看“能不能跑”，还要看“跑得怎么样”。

五、时间复杂度：为什么我们不直接比较运行秒数

在这里插入图片描述

很多初学者会问：
既然算法效率重要，为什么不直接说“这个程序运行了 0.02 秒”？

因为程序的实际运行时间受太多因素影响：

机器性能不同
编程语言不同
编译器优化不同
输入数据不同
系统环境不同

为了抓住算法本身的效率，我们引入时间复杂度。

1. 时间复杂度的核心思想

时间复杂度不是在算“准确运行时间”，而是在分析：

当输入规模 n 增大时，算法执行次数如何增长。

通常记作：

$T (n) = O (f (n))$

意思是：当问题规模增大时，算法执行时间的增长趋势与 (f(n)) 同阶。

重点是“增长趋势”，不是某台电脑上的精确秒数。

2. 分析时间复杂度的标准步骤

做题时建议固定按这五步来：

第一步：确定问题规模 (n)

例如：

数组长度
结点个数
顶点数、边数
输入字符串长度

第二步：选定基本操作

基本操作是算法中重复执行、最能代表代价的核心操作。

例如：

比较一次关键字
数组访问一次
指针移动一次

第三步：统计基本操作执行次数

这一步是核心。
分析循环、递归、分支中关键语句一共执行了多少次。

第四步：写出 (T(n)) 的数量级

保留主导项，忽略低阶项和常数项。

例如：

$\Rightarrow O(n)$
$n2+5n+7⇒O(n2)n^2+5n+7 \Rightarrow O(n^2)$

第五步：给出结论并说明原因

考试里不要只写一个结果，最好顺手解释一句：
“主导项为 $n^2$ ，故时间复杂度为 $O(n^2)$ 。”

3. 为什么可以忽略常数和低阶项

因为复杂度研究的是规模变大时的趋势。

例如：

$1000 n$ 和 $n$ 虽然常数不同，但同属于线性增长；
$n^2+n$ 在 $n$ 很大时，主要由 $n^2$ 决定。

这就是大 O 记号的思想：
抓主要矛盾，不纠缠细节噪声。

六、线性查找：理解时间复杂度最经典的例子

在这里插入图片描述

设在线性表 A[0...n-1] 中查找值为 k 的元素：

i = 0
while i < n and A[i] != k:
    i = i + 1
if i < n:
    return i
else:
    return -1

这个算法非常适合练习复杂度分析。

1. 最好情况

如果第一个元素就是目标值，那么只比较 1 次就找到了。

所以最好情况时间复杂度为：

$O (1)$

2. 最坏情况

如果目标在最后一个位置，或者根本不存在，就要比较 (n) 次。

所以最坏情况时间复杂度为：

$O (n)$

3. 平均情况

如果目标可能出现在任意位置，平均比较次数大约与 (n) 成正比。

所以平均时间复杂度仍然是：

$O (n)$

4. 这个例子真正要学会什么

不是只背“顺序查找是 (O(n))”这句话，而是学会：

复杂度和输入规模有关；
复杂度也和数据分布有关；
同一个算法可以区分最好、最坏、平均情况。

这在后续学习排序、查找、图算法时都非常重要。

七、常见时间复杂度量级，一定要形成直觉

常见量级从小到大大致是：

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

理解这些量级，比死记更重要。

1. (O(1))

常数时间。
例如数组按下标访问一个元素。

含义不是“只执行一次”，而是“执行次数不随 (n) 增长而增长”。

2. (O(\log n))

对数时间。
常见于“每次把问题规模缩小一半”的算法，例如二分查找。

3. (O(n))

线性时间。
常见于单层遍历。

4. (O(n\log n))

比线性稍大，但通常仍然是很优秀的复杂度。
很多高效排序算法（如归并排序、堆排序）都在这个量级。

5. (O(n^2))

平方级复杂度。
双重循环很常见地落在这个量级。

6. (O(2^n))、(O(n!))

指数级、阶乘级。
当 (n) 稍微变大就非常可怕，通常只适合很小规模问题。

八、做复杂度题时常用的两个运算法则

教材中常见两条规律：

1. 加法规则

如果一个算法由两个部分组成：

$T(n)=T_1(n)+T_2(n)$

那么总复杂度取决于增长更快的那一项：

$O(\max(f(n), g(n)))$

比如：

前一段是 (O(n))
后一段是 (O(n^2))

总复杂度就是 (O(n^2))。

2. 乘法规则

如果一个操作嵌套在另一个操作中：

$T(n)=T_1(n)\times T_2(n)$

复杂度通常相乘。

例如双重循环：

外层循环执行 (n) 次
内层循环执行 (n) 次

总复杂度就是：

$O(n^2)$

九、空间复杂度：别只盯着运行时间

在这里插入图片描述

算法效率不只有时间，还有空间。

空间复杂度通常记为：

$S (n) = O (g (n))$

它描述的是：
算法在运行过程中额外占用的存储空间随问题规模增长的变化趋势。

注意关键词：额外占用。
输入数据本身通常不算在辅助空间里，重点看为实现算法另外开辟了多少空间。

1. (O(1)) 空间

如果算法只用到少量固定数量的辅助变量，例如：

若干计数器
若干临时变量
交换时的中间变量

那么空间复杂度就是：

$O (1)$

2. (O(n)) 空间

如果算法额外申请了一个与输入规模成正比的数组、队列、栈等辅助结构，那么空间复杂度通常是：

$O (n)$

例如：

复制一个长度为 (n) 的数组
开一个辅助数组做归并
用显式栈保存 (n) 个状态

3. 递归也会消耗空间

这是很多人容易忽略的一点。

递归调用会产生函数调用栈。
如果递归深度是 (n)，那么即使代码里没有显式开数组，也可能有：

$O (n)$

的栈空间消耗。

十、时间复杂度与空间复杂度的关系：常常是在做权衡

现实中，很多算法不是“时间和空间都最优”，而是在做取舍。

例如：

哈希表通常用更多空间换更快查找；
原地算法节省空间，但实现可能更复杂；
动态规划常常用空间换时间，避免重复计算。

所以分析算法时，最好形成这样的意识：

优化一个维度，往往要看另一个维度是否付出了代价。

十一、最容易混淆的几个点，一次说清

1. 逻辑结构不等于存储结构

线性表是逻辑结构；
顺序表、链表是存储实现。

也就是说：

同一个逻辑结构，可以有不同存储结构。

2. 时间复杂度不是精确运行时间

(O(n)) 不等于“真的用了 n 秒”。
它表示的是增长趋势，而不是具体数值。

3. (O(1)) 不表示只有一条语句

只要操作次数不随 (n) 增长，就可以是 (O(1))。
即使里面有 100 条固定语句，仍然可能是 (O(1))。

4. 平均复杂度不能“想当然”

平均复杂度需要建立在某种概率分布假设上。
不是随手把最好和最坏一平均就结束。

5. 递归算法的空间复杂度不能漏掉调用栈

这是做题时很常见的失分点。

附：一页复习版

你只剩 5 分钟时，记这几个点

数据结构 = 数据元素 + 关系
三要素 = 逻辑结构、存储结构、运算
逻辑结构四类 = 集合、线性、树、图
存储结构四类 = 顺序、链式、索引、散列
算法五特性 = 有穷、确定、可行、输入、输出
评价算法 = 正确性 + 可读性 + 健壮性 + 时空效率
时间复杂度看增长趋势，不看精确秒数
空间复杂度看辅助空间，不只看代码里有没有数组

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2303_80022567/article/details/159834598

数据结构第一章复习：基本概念与算法复杂度分析

一、为什么第一章非常重要

二、先把最基础的几个概念分清

1. 数据（Data）

2. 数据元素（Data Element）

3. 数据项（Data Item）

4. 数据对象（Data Object）

5. 数据类型（Data Type）

6. 数据结构（Data Structure）

三、数据结构的三要素

1. 逻辑结构：先看“关系是什么”

（1）集合结构

（2）线性结构

（3）树形结构

（4）图状结构或网状结构

2. 存储结构：再看“在计算机里怎么存”

（1）顺序存储

（2）链式存储

（3）索引存储

（4）散列存储（哈希存储）

3. 数据的运算：最后看“你要对它做什么”

4. 抽象数据类型（ADT）是什么

四、算法的基本概念：算法不只是“代码”

1. 什么是算法

2. 一个算法通常具备五个特性

（1）有穷性

（2）确定性

（3）可行性

（4）输入

（5）输出

3. 怎样评价一个“好算法”

正确性

可读性

健壮性

高效率与低存储量需求

五、时间复杂度：为什么我们不直接比较运行秒数

1. 时间复杂度的核心思想

2. 分析时间复杂度的标准步骤

第一步：确定问题规模 (n)

第二步：选定基本操作

第三步：统计基本操作执行次数

第四步：写出 (T(n)) 的数量级

第五步：给出结论并说明原因

3. 为什么可以忽略常数和低阶项

六、线性查找：理解时间复杂度最经典的例子

1. 最好情况

2. 最坏情况

3. 平均情况

4. 这个例子真正要学会什么

七、常见时间复杂度量级，一定要形成直觉

1. (O(1))

2. (O(\log n))

3. (O(n))

4. (O(n\log n))

5. (O(n^2))

6. (O(2^n))、(O(n!))

八、做复杂度题时常用的两个运算法则

1. 加法规则

2. 乘法规则

九、空间复杂度：别只盯着运行时间

1. (O(1)) 空间

2. (O(n)) 空间

3. 递归也会消耗空间

十、时间复杂度与空间复杂度的关系：常常是在做权衡

十一、最容易混淆的几个点，一次说清

1. 逻辑结构不等于存储结构

2. 时间复杂度不是精确运行时间

3. (O(1)) 不表示只有一条语句

4. 平均复杂度不能“想当然”

5. 递归算法的空间复杂度不能漏掉调用栈

附：一页复习版

你只剩 5 分钟时，记这几个点

评论

评论列表

微信小程序

QQ小程序

关于作者