# 基本概念和术语
# 一、识记概念（一句话记忆）
- 数据：所有能被计算机处理的信息（如数字、文字、图像等）
- 数据元素：数据的"基本单位"，比如学生记录中的一个学生信息
- 数据项：数据元素的"最小组成单位"，比如学生记录中的学号、姓名等
- 数据结构：数据元素之间的"关系+操作方式"（如排队是线性结构，家族树是树结构）
- 逻辑结构：数据元素的"抽象关系"（如线性、树状、网状关系）
- 存储结构：数据在计算机中的"实际存储方式"（如数组连续存储，链表分散存储）
- 基本操作：对数据结构的常见动作（如插入、删除、查找）
- 集合结构：元素之间"没有特定关系"的松散组织（如一袋杂粮）
- 线性结构：元素"一对一"排列（如排队、链表）
- 树结构：元素"一对多"的层级关系（如公司组织架构）
- 图结构：元素"多对多"的网状关系（如地铁线路图）
- 抽象数据类型：对数据结构的"功能描述"（只关心能做什么，不关心具体实现）
# 二、领会关系与影响
# 1. 数据项之间的关系
- 数据项是不可分割的最小单位，多个数据项组成一个数据元素。 例子：学生记录是一个数据元素，包含学号、姓名、成绩等数据项。
# 2. 逻辑结构 vs 存储结构
- 逻辑结构是抽象的"关系蓝图"（如排队的顺序），存储结构是具体的"实现方式"（如数组或链表）。 例子：线性逻辑结构可以用数组（连续存储）或链表（分散存储）实现。
# 3. 存储结构对基本操作的影响
- 顺序存储（如数组）：访问快（直接通过下标），但插入/删除慢（需移动元素）。
- 链式存储（如链表）：插入/删除快（改指针），但访问慢（需遍历）。
- 不同存储方式直接影响算法效率，需根据问题选择。
# 4. 4种基本存储方法
| 存储方式 | 特点 | 适用场景 |
|---|---|---|
| 顺序存储 | 内存连续，下标访问 | 需频繁查询的线性结构（如数组） |
| 链式存储 | 内存分散，指针连接 | 需频繁插入/删除的线性结构（如链表） |
| 索引存储 | 额外建立索引表 | 快速查找（如数据库索引） |
| 散列存储 | 通过哈希函数定位 | 快速插入和查询（如字典） |
# 5. 线性 vs 非线性结构
- 线性结构：元素"单线串联"，如数组、栈、队列。
- 非线性结构：元素存在"多分支关系"，如树（一对多）、图（多对多）。
# 三、一句话总结
- 逻辑结构是灵魂（定义关系），存储结构是肉体（实现方式），二者结合决定数据结构的性能。
- 选择存储结构时，需权衡时间效率（操作速度）和空间效率（内存占用）。
# 算法和算法分析
# 一、识记概念（一句话记忆）
- 算法：解决特定问题的明确步骤（如菜谱：先放油，再炒菜，最后加盐）
- 算法5个特性：
- 有穷性：步骤有限（菜谱不能无限循环）
- 确定性：每一步无歧义（"加盐少许"需明确克数）
- 输入：可能有0个或多个输入（比如做菜需要食材）
- 输出：至少1个结果（做出一道菜）
- 可行性：每一步可执行（不能要求"徒手劈开钢板"）
- 问题规模：问题的输入量（如排序10个数 vs 1亿个数）
- 时间复杂度：算法执行时间随问题规模增长的趋势（如O(n)表示时间与数据量成正比）
- 空间复杂度：算法占用内存随问题规模增长的趋势（如O(1)表示内存固定）
- 大O表示法：用
O(f(n))表示复杂度的上界（如O(n²)比O(n)慢） - 增长函数：描述复杂度随问题规模变化的函数（如n²增长比n快）
# 二、领会核心关系
# 1. 算法复杂度分析
- 时间复杂度：关注循环次数（如
for i in range(n)是O(n)） - 空间复杂度：关注额外变量（如排序时临时变量是O(1)）
- 大O表示法忽略常数：O(2n)和O(n)都简化为O(n)（只关注趋势，不纠结具体系数）
# 2. 常见复杂度级别（按效率排序）
| 复杂度 | 增长速度 | 例子 |
|---|---|---|
| O(1) | 常数级 | 直接访问数组元素 |
| O(log n) | 对数级 | 二分查找 |
| O(n) | 线性级 | 遍历数组 |
| O(n log n) | 线性对数级 | 快速排序 |
| O(n²) | 平方级 | 双重循环遍历 |
# 3. 复杂度分析技巧
- 单层循环：O(n)（如遍历数组）
- 嵌套循环：O(n²)（如矩阵相乘）
- 递归：看递归深度（如斐波那契数列递归是O(2^n)）
# 三、简单应用示例
# 例1：分析以下代码的时间复杂度
for i in range(n): # 循环n次 → O(n)
print(i)
for j in range(n): # 循环n次 → O(n)
print(j)
总时间复杂度：O(n) + O(n) = O(n)（常数项忽略）
# 例2：分析嵌套循环
for i in range(n): # 外层循环n次
for j in range(n): # 内层循环n次
print(i, j)
时间复杂度：O(n) × O(n) = O(n²)
# 例3：二分查找
left, right = 0, n-1
while left <= right: # 每次范围减半 → O(log n)
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid -1
时间复杂度：O(log n)（每次问题规模减半）
# 四、一句话总结
- 算法是解决问题的步骤，复杂度分析帮你预判效率（时间）和资源消耗（空间）。
- 大O表示法是算法界的"速度标尺"，只关注最坏情况下的增长趋势。