基本概念

数据结构

数据结构 (Data Structure) 是带 结构 的数据元素的集合，“结构 指数据元素之间存在的关系

数据结构包括 逻辑结构 和 存储结构 两个层次，还有 数据运算 这个法则。

逻辑结构

逻辑结构脱离于计算机，是一种 从具体问题中抽象出来的 数学模型

该结构 需要两个构成因子：

1. 数据

2. 关系

常见类型

上面四种结构以 某班级学生作为数据对象 作为例子 来分别考察数据元素之间的关系

集合结构

数据元素之间除了 “ 属于同一集合 的关系外，别无其他关系。

例如，确定一名学生 是否为 班级成员，只需将班级看做一个集合结构。

线性结构

数据元素之间存在一对一的关系。

例如，将学生信息数据按照其入学报到的时间 先后顺序 进行排列，将组成一个线性结构。

树结构

数据元素之间存在一对多的关系。

例如，在班级的 管理体系 中，班长管理多个组长，每位组长管理多名组员，构成树形结构

图结构

数据元素之间存在多对多的关系。

例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构

层次图

物理结构

数据对象在计算机中的存储表示 称为数据的 存储结构，也称为 物理结构

数据元素在计算机中有两种基本的存储结构，分别是 顺序存储结构 和 链式存储结构

简单来讲就是 数组 和 链表

顺序存储结构

• 物理位置相邻 表示逻辑关系
• 占用一片连续的存储空间
• 支持随机存取（按下标 $O(1)$ 查找）

链式存储结构

• 借助指针/引用 表示逻辑关系
• 结点存储空间不一定连续（可连续可不连续）
• 支持顺序存取（必须从头节点开始找）

算法分析

算法的定义及特性

算法 (Algorithm) 是为解决某类问题而规定的 有限长操作序列

五个特性

特性	说明
有穷性	执行有穷步后结束，每步在有限时间内完成
确定性	每步操作有确切规定，无二义性
可行性	所有操作可通过已实现的基本操作有限次执行完成
输入	零个或多个输入（通过形参传递）
输出	一个或多个输出（通过返回值或引用形参返回）

评价标准

• 正确性：合理输入下得到正确结果
• 可读性：便于理解与交流（优先于机器可执行性）
• 健壮性：非法输入能适当处理
• 高效性：时间高效（时间复杂度）和空间高效（空间复杂度）

时间复杂度

定义：算法中基本语句重复执行的次数是问题规模 $n$ 的某个函数 $f(n)$，记作 $T(n)=O(f(n))$，表示算法执行时间的增长率和 $f(n)$ 的增长率相同。

符号 $O$ 描述增长率的上限，即 $T(n)\le C\cdot f(n)$（当 $n\ge n_0$ 时）

一条语句的 重复执行次数 称作 语句频度（Frequency Count)

一个算法的执行时间大致上等于其 所有语句执行时间的总和，而语句的执行时间则为该条语句的 语句频度 和 执行一次所需时间 的乘积。

注意

由于语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此 语句执行一次实际所需的具体时间 是与机器的软、硬件环境（如机器速度、编译程序质量等）密切相关的。

所以，所谓的算法分析 并非精确统计算法实际执行所需时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。

分析方法

1. 找出基本语句（频度最大的语句）
2. 计算基本语句的频度 $f(n)$
3. 取数量级：忽略低次幂项和最高次幂系数，$T(n)=O(n^m)$（$m$ 为最高次幂）

常见复杂度

复杂度	名称	示例
$O(1)$	常量阶	单条语句、与 $n$ 无关的循环
$O({\log }_{2}n)$	对数阶	for(i=1; i<=n; i=i*2)
$O(n)$	线性阶	单层循环
$O(n{\log }_{2}n)$	线性对数阶	快速排序等
$O(n^2)$	平方阶	双层循环
$O(n^3)$	立方阶	三层循环
$O(2^n)$	指数阶	效率极低，$n$ 稍大即不可用
$O(n!)$	阶乘	效率最低

口诀 常对幂指阶

最好、最坏和平均时间复杂度

• 最好：计算量可能达到的最小值
• 最坏：计算量可能达到的最大值（最常用，作为执行时间的上界）
• 平均：所有可能情况按等概率的加权平均值（通常难以确定）

空间复杂度

定义：算法所需存储空间的度量，记作 $S(n)=O(f(n))$

• 只分析辅助空间：除输入数据外额外占用的存储空间
• 原地工作：辅助空间为 $O(1)$

示例

数组逆序，借助一个临时变量 $t$ 为 $O(1)$，借助大小为 $n$ 的辅助数组为 $O(n)$

时间复杂度和空间复杂度往往相互制约，但通常以时间复杂度为主要衡量指标。

Relax 1000 题

刷新对 逻辑结构 和 存储结构 的认知

Caution

打个比方：

🏠 逻辑结构 = 房子的设计图
🧱 存储结构 = 房子的建造材料（砖头、木头、钢筋）

设计图 不依赖用什么材料建造，逻辑结构独立于存储结构
材料 是为了盖这栋楼而选的，存储结构不能脱离逻辑结构独立存在

具体例子，实现一个栈（逻辑结构：后进先出）：

• 存储结构 A：数组实现的栈
• 存储结构 B：链表实现的栈

逻辑上都是”栈”，push/pop 行为一样；选哪种存储由需求决定，不是存储结构自己独立决定的。

反过来，不可能先有一块”链表内存布局”，再说它独立于任何逻辑结构——它一定是为表达某种逻辑关系才这样排列。

“独立”是逻辑对存储的单向独立，不是互相独立。