单元1
算法+数据结构 = 程序
- 算法：如何让计算机分析这些数据？
- 数据结构：如何把这些数据表示给计算机？
- 程序：如何让计算机明白我要做什么？
网课地址：数据结构基础
🧠 数据结构与算法效率总览
一、📦 抽象数据类型（ADT：Abstract Data Type）
抽象数据类型定义了一类数据的逻辑结构和操作方式，它不依赖具体的实现方式，是算法设计的基础。
✨ ADT 特点：
- 封装性：隐藏内部存储与操作细节，只暴露接口
- 独立性：实现方式灵活（可用数组、链表等）
- 通用性：跨语言、跨平台适用
📚 常见 ADT 与实现方式及应用
| ADT名称 | 描述 | 常见实现方式 | 应用场景举例 |
|---|---|---|---|
| 数组 | 固定大小，顺序排列 | 顺序存储 | 图像处理、表格数据 |
| 链表 | 节点动态链接 | 单/双向链表 | 内存分配、编辑器缓冲区 |
| 栈 | 后进先出（LIFO） | 数组、链表 | 函数调用、撤销操作 |
| 队列 | 先进先出（FIFO） | 链表、循环数组 | 消息调度、打印系统 |
| 集合 | 无序不重复元素集合 | 哈希表、树结构 | 数据去重、元素管理 |
| 映射（Map） | 键值对集合 | 哈希表、搜索树 | 参数配置、缓存索引 |
| 堆（Heap） | 特殊优先队列结构 | 完全二叉树 | 优先任务调度、TOP-k问题 |
| 树（Tree） | 分层父子关系结构 | 二叉树、AVL树等 | 文件系统、数据库索引 |
| 图（Graph） | 顶点与边构成关系网 | 邻接表、邻接矩阵 | 地图导航、社交关系网络 |
二、📊 数据结构逻辑组织层级关系
根据元素之间的逻辑关系，可分为线性与非线性结构：
🧩 线性结构
- 元素一对一排列
- 包括：线性表、栈、队列、串（字符串）
🌲 非线性结构
- 元素存在一对多或多对多关系
- 包括：
| 类型 | 示例 |
|---|---|
| 树 | 二叉树、搜索树、Huffman 树等 |
| 图 | 有向图、无向图、加权图等 |
✅ 层级包含关系：图 ⊇ 树 ⊇ 二叉树 ⊇ 线性表
三、⚙️ 算法类型与应用分类
🧠 按设计思想分类
| 类型 | 描述 | 应用举例 |
|---|---|---|
| 贪心算法 | 每步选局部最优，期望整体最优 | Huffman编码、区间调度 |
| 分治算法 | 分成子问题，递归求解再合并 | 快速排序、归并排序 |
| 动态规划 | 保存子结果，避免重复计算 | 最短路径、背包问题 |
| 回溯算法 | 穷举可能，失败则回退 | 八皇后、排列组合 |
| 分支定界 | 回溯 + 剪枝条件提升效率 | TSP、约束优化问题 |
| 随机算法 | 引入随机性提高效率或成功率 | 快速选择、蒙特卡洛法 |
🎯 按应用领域分类
- 排序类：快排、归并、堆排序
- 查找类：二分查找、哈希检索
- 图论类：DFS、BFS、最短路径、MST
- 字符串类：KMP、Trie 树、正则匹配
- 数学优化类：递归、回溯、动态规划
- 机器学习类：决策树、聚类、神经网络
- 加密与安全类：哈希、RSA、AES
四、📈 时间复杂度分类（整合表）
时间复杂度是衡量算法效率的重要指标，描述算法执行时间与输入规模 n 之间的关系。
| 时间复杂度 | 描述 | 示例算法 |
|---|---|---|
| O(1) | 常数时间，极快 | 哈希查找、数组访问 |
| O(log n) | 对数时间，逐步缩小问题规模 | 二分查找、树搜索 |
| O(n) | 线性增长 | 遍历数组、线性查找 |
| O(n log n) | 高效排序类 | 快速排序、归并排序 |
| O(n²) | 二重循环或嵌套结构 | 冒泡排序、回文检测 |
| O(2ⁿ) | 指数级复杂度 | 回溯搜索、子集问题 |
| O(n!) | 阶乘级复杂度 | 全排列穷举、TSP问题 |
注：O 表示的是最坏情况的上界估计
🧠 五、ADT 与典型算法对应关系
抽象数据类型不仅决定了数据的组织方式，也直接影响算法设计。以下是常见 ADT 与其对应算法：
| 抽象数据类型 | 典型算法 |
|---|---|
| 栈 | 括号匹配、表达式求值、深度优先搜索（DFS） |
| 队列 | 广度优先搜索（BFS）、轮转调度、消息排队 |
| 数组 | 排序（快排、归并）、滑动窗口、双指针遍历 |
| 链表 | 插入与删除操作、链表反转、快慢指针查找 |
| 堆 | 堆排序、优先队列调度、Top-K 问题 |
| 哈希表（Map） | 常数时间查找、去重处理、频率统计 |
| 树结构 | 前中后序遍历、最近公共祖先、区间查询 |
| 图结构 | 最短路径搜索、拓扑排序、连通性检测 |
📘 总结与学习建议
- 使用合适的数据结构可以大幅提升算法效率
- 掌握算法的设计思想，有助于构建通用问题求解框架
- 分析时间复杂度，能有效评估程序性能与可扩展性
- 推荐逐步掌握：线性结构 → 树与图 → 高级算法 → 实战题目
课后习题 - 数据结构概论
以下属于非线性数据结构
- 散列表。
- 向量，虽然底层是线性存储，作为抽象数据类型，其分类有时会有细微差别，但通常也归入线性结构（动态数组）。
是否随着技术迭代，分类标准会有所变化？需结合具体应用场景理解，曾经散列表和向量都是线性的数据结构。
代码的时间复杂度 和 大O（Big-O）
以下说法是正确的：
- 函数f(n) = O(g(n))，当常数a足够大时，不一定有函数 g(n)= O(af(n))
- 如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))
大O符号是算法分析中用来描述函数增长趋势（或“上界”）的数学工具。它关注的是当输入规模 n 变得非常大时，算法的运行时间或空间占用如何增长。
代码分析
这段代码的时间复杂度是 O(n²)。
for (i=0, length=1; i<n-1; i++) {
for (j = i+1; j<n && a[j-1]<=a[j]; j++)
if(length < j-i+1)
length = j-i+1;
}
功能：这段代码的目的是在数组 a 中找到最长的非递减连续子序列的长度（length）。
- 外层循环
i从0到n-2，表示尝试以a[i]作为子序列的起始位置。 - 内层循环
j从i+1开始，只要a[j-1] <= a[j]（即当前元素不小于前一个元素），就继续向后扫描，从而扩展以i为起点的非递减子序列。 length记录了当前找到的最长子序列长度。
时间复杂度分析
- 外层循环：执行
(n-1)次，即 O(n)。 - 内层循环：对于每一个
i，内层循环j的执行次数取决于从位置i开始的非递减序列有多长。
最坏情况发生在整个数组是完全非递减的（例如：[1, 2, 3, 4, 5]）。
- 当
i=0时，内层循环j从1到n-1，执行约n-1次。 - 当
i=1时，内层循环j从2到n-1，执行约n-2次。 - …
- 当
i=n-2时，内层循环j从n-1开始，最多执行 1 次。
因此，内层循环的总执行次数约为：
(n-1) + (n-2) + ... + 1 = (n-1)*n/2 ≈ n²/2
这符合 O(n²) 的时间复杂度。
结论
尽管在某些特定输入（如完全递减的数组）下，内层循环可能很快退出，导致时间复杂度接近 O(n)，但在最坏情况下（数组非递减），时间复杂度为 O(n²)。因此，我们说这段代码的时间复杂度是 O(n²)。