introduction-to-algorithms
Mostly AI generated, but well organized.
-
Introduction to Algorithms 算法导论
重点 第一章 What is Algorithm 1. 算法的概念 2. 算法定义中的 5 个性质: 输入, 输出, 确定性, 有穷性, 有效性 第二章 算法设计与分析基础 1. 如何做算法设计, 算法分析 1. 基本思想 2. 具体过程 3. 伪代码 4. 时空间复杂度 5. 需要问题具有的性质 6. 典型例子...
-
Dynamic Programming 动态规划
hallmark 1 "An optimal solution to a problem contains optimal solutions to subproblems." 一个问题的最优解, 包含其子问题的最优解. hallmark 2 "A recursive solution contains a 's...
-
Shortest Path 最短路径
单源最短路 1. Dijkstra's Algorithm 迪杰斯特拉算法 2. Bellman Ford Algotithm 贝尔曼福特算法可以检测负环的存在, 解决了迪杰斯特拉在有负环情况失效的问题. p.s. 注意时间复杂度差异 3. 差分约束 所有点对最短路 1. 多次执行[单源最短路] 2. Floyd...
-
BFPRT - Median of Medians BFPRT选择算法
核心任务: Top K问题: 在一个数组中找第k小/大的元素 隶属于任务: Order Statistic 顺序统计量 参考方法: Quick Select 快速选择 算法实现: step1: 分组, 5个元素一组 step2: 找每组的中位数(给每组的5个数排序) step3: 找中位数中的中位数pivot s...
-
Backtracking 回溯法
Backtracking 回溯法 回溯法 是在问题的 解空间树 上做 深度优先搜索，并用 剪枝函数 提前丢弃不可能得到可行解或最优解的子树。 它的本质不是“递归”，而是： $$ \text{解空间树} + \text{DFS} + \text{剪枝函数} $$ 1. 基本定位 回溯法适合处理组合搜索问题。复杂问题...
-
Hashing I 哈希 ChatGPT-summarized
Lecture 7 — Hashing（考前速记版） 一、易错点修正（重点） 1. 区分 $O(1)$ 与 $\Theta(1)$ Direct access table 的操作时间是： $$ \Theta(1) $$ 强调的是 严格常数时间 ，而不是宽松的 $O(1)$。 2. $T[k]$ 存的是 recor...
-
Ford-Fulkerson Algorithm 福特福克森算法
Ford Fulkerson Algorithm 福特福克森算法 1. 基本思想 Ford Fulkerson Algorithm 是求解 Maximum Flow 最大流 的经典增广路方法。 核心思想： 从零流开始，只要还能在Residual Network 残量网络中找到一条从源点 $s$ 到汇点 $t$ 的...
-
Order Statistic 顺序统计量
核心任务: Top K问题: 在一个数组中找第k小/大的元素 实现方法: 1. Quick Select 快速选择 2. BFPRT Median of Medians BFPRT选择算法 总结 Quick Select 其实就是只走一边的Quick Sort. Quick Select 虽然worst case...
-
Asymptotic Notation Tips
Asymptotic Notation Tips 核心结论 渐进记号写在 右边 ，通常表示“某个具体函数属于这个渐进函数集合”；写在 左边 ，通常表示“对这个集合中的任意函数，右边结论都成立”。 渐进记号中的等号不是普通等号，而是一种 单向记号滥用 。 严格理解时，应把： $$ f(n) O(g(n)) $$ 看...
-
Asymptotic Notation and Analysis
Asymptotic Notation and Analysis 渐近记号与渐进分析 渐进分析（asymptotic analysis）研究当输入规模 $n\to\infty$ 时，算法运行时间或空间使用量的增长趋势。 它忽略机器相关常数、低阶项和实现细节，关注增长阶。 渐近记号（asymptotic notat...
-
Divide & Conquer 分治
Divide & Conquer 分治 分治策略把一个规模为 $n$ 的问题拆成若干个规模更小、结构相同或相近的子问题，递归求解子问题，再把子问题的解合并成原问题的解。 标准流程是： Divide → Conquer → Combine 。 1. 基本思想 分治法（Divide and Conquer）是一种算法...
-
Iterating the Recurrence 迭代展开法
Iterating the Recurrence 迭代展开法 迭代展开法（Iterating the Recurrence / Iteration Method） 是求解递归式的一种直接方法：不断把递归项继续代入自身，直到规模下降到边界条件，然后把每一轮产生的非递归代价求和。 它的核心不是“套公式”，而是把 $$...
-
Master Method 主方法
Master Method 主方法 主方法（Master Method） 是求解一类分治递归式的快速判定工具。它适用于形如 $$ T(n) aT(n/b)+f(n) $$ 的递归式，其中 $a\ge 1$，$b 1$ 为常数，$f(n)$ 渐近非负。核心是比较 叶子总规模 $n^{\log b a}$ 与 每层非...
-
Recursion Tree Method 递归树法
Recursion Tree Method 递归树法 递归树法（Recursion Tree Method） 是求解递归式的一种直观方法：把递归式展开成一棵树，每个结点表示一个子问题的非递归代价；然后逐层求和，最后把所有层的代价相加，得到 $T(n)$ 的渐近界。 1. 基本思想 递归式通常来自 Divide a...
-
What is Algorithm
算法（Algorithm）的定义： 算法是一个 良定义的计算过程 ：它接收某个值或一组值作为 输入 ，经过一系列明确的 计算步骤 ，产生某个值或一组值作为 输出 。换句话说，算法就是把输入转换为输出的一组有限、明确的操作步骤。 PPT 中的原文表述为： algorithm is “any well defined...
-
Substitution Method 代入法
Substitution Method 代入法 代入法（Substitution Method） 是求解递归式的一种通用方法：先猜测递归式的渐近界，再把猜测代入递归式，用数学归纳法证明猜测成立，最后选择足够大的常数处理残差项和初始条件。 1. 基本思想 代入法的核心流程可以概括为三步： 1. 猜测解的形式 ：例如...
-
Branch and Bound 分支限界法
Branch and Bound 分支限界法 course note
-
Binary Search Tree 二叉搜索树
Binary Search Tree 二叉搜索树 二叉搜索树 （Binary Search Tree, BST）通过维护“左子树关键字更小、右子树关键字更大”的局部有序性，使查找、插入、删除等动态集合操作沿一条根到叶的路径完成。 所有基本操作的时间复杂度均依赖树高 $h$：一般为 $O(h)$。树较平衡时 $h ...
-
0-1 Knapsack Problem
0 1 Knapsack Problem（0 1 背包问题） 对每件物品只有“选择”和“不选择”两种决策。动态规划按照物品逐个扩展状态，对两种决策产生的价值取最大值。 二维实现的时间复杂度为 $\Theta(nW)$、空间复杂度为 $\Theta(nW)$；使用滚动数组后，空间可优化为 $\Theta(W)$。 ...
-
Bucket Sort 桶排序
Bucket Sort 桶排序 桶排序先依据关键字范围将元素分配到若干个 有序的桶 中，再分别排序每个桶，最后按桶的顺序连接结果。 当 $n$ 个输入元素独立、均匀地分布在 $0,1)$ 上，使用 $n$ 个桶并在桶内执行 [插入排序 时，期望时间复杂度为 $\Theta(n)$；但当大量元素集中到同一个桶中时，...
-
Counting Sort 计数排序
Counting Sort 计数排序 计数排序（Counting Sort） 是一种不比较元素大小的整数排序算法。对于长度为 $n$、键值范围大小为 $k$ 的输入，其时间复杂度为 $\Theta(n+k)$。当 $k O(n)$ 时，算法具有线性时间复杂度 $\Theta(n)$。 1. 问题定义 给定包含 $...
-
Activity Selection 活动选择问题
Activity Selection 活动选择问题 对所有活动按 结束时间从早到晚 排序,然后依次选择与已选活动兼容的活动,即可得到数量最多的互不重叠活动集合。 输入已按结束时间排序:时间复杂度为 $\Theta(n)$。 输入未排序:总时间复杂度为 $O(n\log n)$。 贪心选择: 每次选择当前可选活动中...
-
Floyd-Warshall Algorithm
Floyd Warshall Algorithm Floyd Warshall 是解决 所有顶点对最短路径 （All Pairs Shortest Paths, APSP）的动态规划算法。 它依次允许顶点 0, 1, ..., n 1 作为路径的中间顶点，并使用 $$ dp[i][j] \leftarrow \m...
-
Ford-Fulkerson 方法
Ford-Fulkerson 方法 course note
-
Heap Sort 堆排序
Heap Sort 堆排序 堆排序先把数组组织成一个 最大堆 ，随后反复将堆顶最大元素交换到当前未排序区间的末尾，并缩小堆的有效范围。其最好、平均和最坏时间复杂度均为 $\Theta(n\log n)$，辅助空间为 $O(1)$，但通常 不稳定 。 1. 问题定义 给定一个长度为 $n$ 的可比较元素序列： $$...
-
Insertion Sort 插入排序
Insertion Sort 插入排序 插入排序从左向右维护一个 已经排好序的前缀 ，每次取出下一个元素，将它插入前缀中的正确位置。 最好时间复杂度：$\Theta(n)$ 平均、最坏时间复杂度：$\Theta(n^2)$ 额外空间复杂度：$\Theta(1)$ 特性： 原地、稳定、自适应、在线 适用场景：规模较...
-
Johnson's Algorithm
Johnson's Algorithm 约翰逊算法 Johnson 算法用于求解 所有顶点对最短路径 （All Pairs Shortest Paths, APSP），尤其适合 稀疏图 。 它先用一次 Bellman–Ford 计算势函数 $h$，把所有边重赋权为非负权边；然后从每个顶点运行一次 Dijkstra...
-
Linear Time Sort 线性时间排序
Linear Time Sort 线性时间排序 course note
-
Merge Sort 归并排序
Merge Sort 归并排序 归并排序（Merge Sort） 是一种典型的分治算法：将序列递归地划分为两个子序列，分别排序后，再在线性时间内合并。 最好、平均、最坏时间复杂度均为 $\Theta(n\log n)$ 标准数组实现的辅助空间复杂度为 $\Theta(n)$ 可以实现为 稳定排序 标准数组实现通常...
-
Quick Sort 快速排序
Quick Sort 快速排序 快速排序是一种基于分治法的 比较排序算法 。它先通过 PARTITION 将数组围绕一个枢轴（pivot）原地划分，再递归排序左右两部分。 平均与随机化期望时间：$\Theta(n\log n)$ 最坏时间：$\Theta(n^2)$ 原地分区的数组辅助空间：$\Theta(1)$...
-
Radix Sort 基数排序
Radix Sort 基数排序 基数排序将一个关键字拆分成若干个“位”，逐位进行排序。 本文主要讨论 LSD Radix Sort（最低有效位优先基数排序） ：从最低位到最高位依次处理，并且每一趟必须使用 稳定排序 。 若共有 $n$ 个元素、每个关键字有 $d$ 位、每一位有 $R$ 种可能取值，并使用计数排序...
-
Red-Black Tree 红黑树
Red Black Tree 红黑树 红黑树（Red Black Tree） 是一种通过“结点着色 + 局部旋转 + 重新着色”维持近似平衡的二叉搜索树。 对含有 $n$ 个内部结点的红黑树，其高度满足 $$ h \le 2\log 2(n+1), $$ 因而搜索、插入和删除的最坏时间复杂度均为 $O(\log ...
-
Sorting Algorithms 排序算法
Sorting Algorithms 排序算法 course note
-
Bellman-Ford 最短路径算法
Bellman Ford 最短路径算法 Bellman Ford 算法用于求解 加权有向图中的单源最短路径 。它允许图中存在负权边，并且能够检测从源点可达的负权环。若不存在从源点可达的负权环，算法最多经过 $ V 1$ 轮全边松弛后得到正确结果。 目录 1. 问题定义 2. 基本思想 3. 需要问题具有的性质 4...
-
Dijkstra 最短路径算法
Dijkstra 最短路径算法 Dijkstra 算法用于求解 边权非负的加权图 中的单源最短路径。它采用贪心策略：每次从尚未确定最短距离的顶点中，选择当前距离估计最小的顶点，并将该距离永久确定。 目录 1. 问题定义 2. 基本思想 3. 需要问题具有的性质 4. 核心操作：松弛 5. 具体过程 6. 伪代码 ...
-
Kruskal's Algorithm：最小生成树
Kruskal's Algorithm：最小生成树 Kruskal 算法将所有边按权重从小到大处理；只要当前边连接两个不同的连通分量，就将其加入生成森林并合并这两个分量，直到选出 $ V 1$ 条边。 目录 1. 问题定义 2. 基本思想 3. 具体过程 4. 正确性依据 5. 并查集的作用 6. 伪代码 7. ...
-
Prim's Algorithm：最小生成树
Prim's Algorithm：最小生成树 Prim 算法从任意起点出发，维护一棵不断扩张的树；每一步选择连接”树内顶点”和”树外顶点”的最小权重边，直到所有顶点都被纳入。 目录 1. 问题定义 2. 基本思想 3. 具体过程 4. 正确性依据 5. 伪代码 6. 时空间复杂度 7. 问题需要具有的性质 8. ...
-
最长公共子序列（LCS）
最长公共子序列（LCS） 最长公共子序列（Longest Common Subsequence，LCS）要求元素的 相对顺序保持不变 ，但不要求它们在原序列中连续。 对长度分别为 m 和 n 的两个序列，经典动态规划算法的时间复杂度为 $\Theta(mn)$，空间复杂度为 $\Theta(mn)$。 1. 问题...
-
矩阵连乘（MCM）动态规划
矩阵连乘（MCM）动态规划 给定矩阵链 $A 0A 1\cdots A {n 1}$，设维度数组为 $p [p 0,p 1,\ldots,p n]$，其中 $A i$ 的维度为 $p i\times p {i+1}$。 定义： $$ dp[i][j] \text{计算 }A iA {i+1}\cdots A j\...
-
Minimum Spanning Tree 最小生成树
Prim's algorithm 反证法证明最优子结构 Kruskal's algorithm
-
Network Flow 网络流
Network Flow 网络流 course note
-
Greedy Algorithm 贪心算法
Greedy Algorithm 贪心算法 course note
-
Hashing I 哈希
Direct Access Table 直接寻址表 算法实现 存在问题 Direct access table 用空间换时间的极限方案： 用一个巨大数组，实现真正的 Θ(1) 查找，但通常空间不可接受。 为了解决空间的不可接受性, 推出Hashing Table Hashing Table 哈希表 哈希表由两个部...
-
Quick Select 快速选择
核心任务: Top K问题: 在一个数组中找第k小/大的元素 隶属于任务: Order Statistic 顺序统计量 参考方法: Divide & Conquer 分治 Quick Sort 快速排序 算法实现: step1: 随机选择一个pivot step2: 将数组分为3部分 $O(n)$ step3: ...