单元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）常数时间查找、去重处理、频率统计
树结构前中后序遍历、最近公共祖先、区间查询
图结构最短路径搜索、拓扑排序、连通性检测

📘 总结与学习建议

  • 使用合适的数据结构可以大幅提升算法效率
  • 掌握算法的设计思想，有助于构建通用问题求解框架
  • 分析时间复杂度，能有效评估程序性能与可扩展性
  • 推荐逐步掌握：线性结构 → 树与图 → 高级算法 → 实战题目