目 录CONTENT
笔记-憶夣
以下是
笔记
相关的文章
-
7、算法问题选编 本文介绍了**多线程算法、矩阵运算、数论算法和字符串匹配**四大主题。具体如下： **多线程算法**：讲解动态多线程编程模型，通过`spawn`、`sync`和`parallel for`等关键词实现嵌套并行与并行循环，以斐波那契计算、矩阵乘法（朴素/分治/Strassen）和归并排序为例，分析工作量T₁、持续时间T∞及并行度。 **矩阵运算**：阐述LUP分解（PA=LU）及其高斯消元实现，并说明基于LUP分解在Θ(n³)时间内求解矩阵逆的方法。 **数论算法**：给出欧几里得算法及其扩展形式用于计算最大公约数与贝祖系数，介绍模线性方程求解算法，以及利用反复平方法实现模取幂运算。 **字符串匹配**：介绍四种方法：朴素匹配（最坏O(nm)）、Rabin-Karp基于滚动哈希的匹配、有限自动机匹配、以及Knuth-Morris-Pratt（KMP）算法通过前缀函数实现Θ(n)匹配时间。 -
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算法；松弛操作统一最短路径算法；增广路径思想贯穿最大流问题。
-
5、高级数据结构 ## 摘要 本文介绍了多种高级数据结构，重点阐述**B树**、**斐波那契堆**和**不相交集合**三种数据结构。 **B树**是为磁盘存储设计的平衡搜索树，节点可拥有大量子节点（分支因子大），因此高度远低于红黑树。B树通过最小度数t约束每个节点的关键字数量（t-1至2t-1），支持查找、插入和删除操作，均可在O(logₜn)时间内完成且仅需O(h)次磁盘访问。插入时采用"沿途预分裂"策略防止回溯；删除时通过借节点或合并子节点保证节点关键字不少于t-1个，同样实现单趟下降完成删除。 **斐波那契堆**由多棵最小堆序的有根树组成，通过环形双向链表连接根节点，支持可合并堆的基本操作及DECREASE-KEY和DELETE操作，部分操作可在O(1)摊还时间内完成。 **不相交集合数据结构**维护一组不相交动态集合，支持MAKE-SET、UNION和FIND-SET三种操作。其高效实现采用不相交集合森林表示，结合"按秩合并"与"路径压缩"两种启发式策略，实现接近O(1)的均摊时间复杂度。
-
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背包与分数背包的对比，揭示了贪心算法的适用边界。最后，文章还利用贪心思想讲解了赫夫曼编码的构造方法。
-
