目 录CONTENT
笔记-憶夣
以下是
笔记
相关的文章
-
-
6、图算法 # 图算法核心内容摘要 本文系统介绍了**四大类图算法**，涵盖图搜索、生成树、最短路径和最大流问题，每种算法均附有Java实现与复杂度分析。 ## 一、图搜索算法 - **图的表示**：邻接链表（适合稀疏图，空间O(V+E)）和邻接矩阵两种标准方式。 - **BFS（广度优先搜索）**：使用FIFO队列逐层探索，时间O(V+E)，可计算**无权最短路径**，生成广度优先树。 - **DFS（深度优先搜索）**：使用递归/栈深入探索，时间O(V+E)，前驱子图形成**森林结构**。产生括号化时间戳，可将边分为**树边、后向边、前向边、横向边**四类。 - **拓扑排序**：基于DFS完成时间逆序排列，时间O(V+E)，仅适用于**有向无环图(DAG)**。 - **强连通分量(SCC)**：两次DFS算法（原图→转置图），时间O(V+E)。 ## 二、最小生成树 - **贪心通用框架**：逐步选取安全边。 - **Kruskal算法**：按边权排序+并查集，时间O(ElgV)。 - **Prim算法**：从单节点扩展+最小优先队列，时间O(ElgV)。 ## 三、最短路径算法 | 算法 | 适用条件 | 时间��杂度 | |------|---------|-----------| | **Bellman-Ford** | 允许负权边，检测负环 | O(VE) | | **DAG最短路径** | 有向无环图，允许负权 | O(V+E) | | **Dijkstra** | 仅非负权边 | O((V+E)lgV) | | **Floyd-Warshall** | 所有结点对（负权边但无负环）| Θ(V³) | | **Johnson** | 稀疏图所有结点对 | O(V²lgV+VE) | 核心思想：**松弛操作**是所有最短路径算法的基础；Bellman-Ford还可求解**差分约束系统**。 ## 四、最大流 - **Ford-Fulkerson方法**：在残存网络中反复寻找增广路径并更新流。基于**最大流最小切割定理**，当残存网络无增广路径时达到最大流。 - **Edmonds-Karp算法**：用BFS选最短增广路径，时间O(VE²)。 - **最大二分匹配**：将二分图转化为流网络（加源点、汇点，单位容量），用最大流求解，时间O(VE)。 > 整体而言，BFS和DFS是图算法的基石；贪心策略驱动MST算法；松弛操作统一最短路径算法；增广路径思想贯穿最大流问题。
-
-
3、数据结构 这篇文章系统介绍了**数据结构**的核心概念与经典实现，主要涵盖以下内容： **动态集合基础**：定义了动态集合的元素结构（关键字、卫星数据、指针属性）以及两大类操作——查询（SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR）和修改（INSERT、DELETE）。 **基本数据结构（第10章）**：详细讲解了**栈**（LIFO，PUSH/POP）、**队列**（FIFO，ENQUEUE/DEQUEUE）和**链表**（搜索O(n)、插入O(1)、删除、哨兵简化边界处理）的原理与数组实现。 **散列表（第11章）**：对比直接寻址与散列方式，介绍了除法散列、乘法散列、全域散列三种散列函数，以及链接法和开放寻址法（线性/二次/双重探查）两种冲突解决策略，并简述了O(1)最坏情况查找的完全散列。 **二叉搜索树（第12章）**：阐述BST性质，给出查找、最大/最小值、前驱/后继、插入和删除的算法与Java实现，插入和删除均为O(h)时间复杂度。 **红黑树（第13章）**：定义红黑树的五条性质，通过旋转维护平���；详述插入修复（三种情况）和删除修复（四种情况）的完整流程，保证所有操作在O(lgn)时间内完成，并附Java完整实现。 **数据结构扩张（第14章）**：以红黑树为基础，通过四步法（选基础结构、定附加信息、验证维护、设计新操作）构建**顺序统计树**（支持按秩选取和求秩，O(lgn)）和**区间树**（支持区间重叠查询，O(lgn)）。 **总结**：文章从基础到进阶，层次清晰地覆盖了栈、队列、链表、散列、BST、红黑树及扩张结构，是一份全面的数据结构学习笔记。
-
2、排序和顺序统计量 ## 文章摘要 本文系统介绍了排序与顺序统计量的核心算法，涵盖以下四部分内容： **1. 排序算法概览**：明确了排序问题的输入输出定义，区分了比较排序（如插入、归并、堆、快速排序）与非比较排序（计数、基数、桶排序）。通过决策树模型证明比较排序的最坏时间下界为 $O(n\log n)$，而特定条件下非比较排序可达 $O(n)$。 **2. 堆排序与优先队列**：堆是一种近似完全二叉树结构，分为最大堆和最小堆。核心操作包括 MAX-HEAPIFY（$O(\log n)$）维护堆性质、BUILD-MAX-HEAP（$O(n)$）构建最大堆，HEAPSORT（$O(n\log n)$）通过反复提取最大值实现排序。优先队列基于堆实现了插入、取最大值、删除最大值及关键字增加等操作。 **3. 快速排序**：采用分治策略，通过 PARTITION 划分子数组并递归排序。最坏情况 $O(n^2)$、最好/平均情况 $O(n\log n)$。随机化版本通过随机选取主元有效规避最坏情况。 **4. 线性时间排序与选择**：计数排序通过计数小于每个元素的个数直接定位，时间 $O(n+k)$；基数排序按位进行稳定的子排序，时间 $O(d(n+k))$；桶排序利用均匀分布假设，平均 $O(n)$。顺序统计量问题可通过随机化选择算法在 $O(n)$ 时间内找到第 $i$ 小元素。
-
4、高级设计和分析技术 本文主要介绍了算法设计与分析中的三种高级技术：动态规划、贪心算法和摊还分析。 **动态规划**适用于存在重叠子问题和最优子结构的最优化问题。文章详细剖析了钢条切割、矩阵链乘法、最长公共子序列和最优二叉搜索树四个经典案例，展示了通过“自底向上”或“带备忘的自顶向下”方法将指数级复杂度降至多项式级（如$O(n^2)$或$O(n^3)$）的过程。 **贪心算法**则通过每步做出局部最优选择来期望获得全局最优解，通常效率更高。文章以活动选择问题为例，阐述了其核心性质——贪心选择性质，并通过0-1背包与分数背包的对比，揭示了贪心算法的适用边界。最后，文章还利用贪心思想讲解了赫夫曼编码的构造方法。
-
