PaperReding：《LLaMA: Open and Efficient Foundation Language Models》
2025/12/17 21:27:21
目录
败者树（Loser Tree）
B树（B-Tree）
排序算法总结
查找算法总结
败者树（Loser Tree）
多路平衡归并排序（胜者树、败者树）算法详解 - C语言中文网
多路归并、败者树、置换-选择排序、最佳归并树 - guanyubo - 博客园
【数据结构】败者树的建树与比较过程-CSDN博客
(99+ 封私信 / 82 条消息) 多路归并排序的时候，为什么要采用败者树？ - 知乎
| 项目 | 内容 |
|---|---|
| 定义 | 一种完全二叉树，用于在多路归并排序中快速选出最小（或最大）元素，减少比较次数。 |
| 核心思想 | 每个非叶子节点记录“失败者”（即比较中较大的值），而胜者向上继续比较，最终根节点记录冠军（最小者）。 |
| 结构特点 | - 叶子节点：存放各归并段的当前元素 - 内部节点：记录失败者索引 - 根节点的父节点：记录冠军（最小者） |
| 建树过程 | 从最后一个叶子节点开始向上调整，依次比较兄弟叶子节点，失败者存入父节点，胜者继续向上。 |
| 调整过程 | 当冠军输出后，从对应归并段读入新元素，沿路径向上与父节点比较，更新失败者和胜者。 |
| 优点 | 比直接比较各归并段首元素更高效，每次调整只需log₂k次比较（k为归并路数）。 |
| 应用场景 | 外部排序（多路归并） |
| 408考点 | - 建树与调整过程 - 比较次数计算 - 与胜者树的区别（败者树无需记录胜者到中间节点） |
B树（B-Tree）
| 项目 | 内容 |
|---|---|
| 定义 | 多路平衡查找树，常用于磁盘等外存数据存储。 |
| 性质 | 1. 每个节点最多有 m 棵子树（m阶B树） 2. 根节点至少有两棵子树（除非为叶子） 3. 非根非叶节点至少有 ⌈m/2⌉ 棵子树 4. 所有叶子出现在同一层，不带信息（实际B+树叶子含信息） |
| 节点结构 | (n, P₀, K₁, P₁, K₂, …, Kₙ, Pₙ)n：关键字数；Kᵢ：关键字；Pᵢ：指向子树的指针 |
| 查找 | 类似二叉查找树，在每个节点内顺序或二分查找，沿指针向下。 |
| 插入 | 先查找插入位置，插入后若节点关键字数 > m-1，则分裂：中间关键字上移，左右分成两个节点。 |
| 删除 | 1. 若在非叶节点，用后继覆盖再删后继 2. 删除后若关键字数 < ⌈m/2⌉-1，则向兄弟借或与兄弟合并 |
| 高度与性能 | 高度 h ≤ logₘ((n+1)/2) + 1，查找、插入、删除磁盘I/O次数为 O(logₘn) |
| 应用场景 | 文件系统、数据库索引 |
| 408考点 | - B树定义与性质 - 插入、删除过程及分裂/合并 - 高度计算与磁盘I/O次数分析 - B树与B+树区别（B+树所有关键字在叶子，叶子链表连接） |
(99+ 封私信 / 82 条消息) 图解：什么是B树？（心中有 B 树，做人要虚心）一文读懂B-树 - 知乎
数据结构：B树、B+树、B*树-CSDN博客
b树，b+树，b-树,红黑树详解一锅端 - 你的雷哥 - 博客园
排序算法总结
【总结】【数据结构】排序-CSDN博客
| 排序方法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 | 小规模或基本有序 |
| 折半插入 | O(n²) | O(n²) | O(1) | 稳定 | 减少比较次数，移动次数不变 |
| 希尔排序 | O(n¹·³) | O(n²) | O(1) | 不稳定 | 中等规模，插入排序改进 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学用，效率低 |
| 快速排序 | O(n log n) | O(n²) | O(log n)~O(n) | 不稳定 | 大规模，内部排序，基于分治 |
| 简单选择 | O(n²) | O(n²) | O(1) | 不稳定 | 教学用 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模，适合取前k个 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 外部排序、链表排序 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 多关键字，位数固定 |
| 外部排序 | 多路归并+败者树 | 依赖磁盘I/O | O(1)缓冲区 | 稳定 | 大文件排序 |
时间/空间复杂度分析
稳定性判断
排序过程模拟（尤其是快排、堆排、归并）
外部排序流程（生成初始归并段、多路归并、败者树优化）
查找算法总结
| 查找方法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|---|
| 顺序查找 | O(n) | O(n) | O(1) | 无序或有序表，简单 |
| 折半查找 | O(log n) | O(log n) | O(1) | 有序顺序表，需随机存取 |
| 分块查找 | O(√n) ~ O(log n) | O(n) | O(1) | 块内无序、块间有序 |
| 二叉查找树 | O(log n) | O(n) | O(n) | 可能退化 |
| 平衡二叉树（AVL） | O(log n) | O(log n) | O(n) | 插入删除需旋转 |
| B树/B+树 | O(logₘ n) | O(logₘ n) | O(n) | 外存查找，m阶B树 |
| 哈希查找 | O(1) | O(n) | O(n) | 冲突影响性能 |
哈希表重点：
构造方法：直接定址、除留余数、平方取中等
冲突处理：开放定址（线性探测、二次探测）、链地址法
性能分析：ASL成功/失败、装填因子 α = n/m
顺序/折半/分块查找的过程与ASL计算
BST/AVL的查找、插入、删除及旋转
B树查找、插入删除过程
哈希函数设计、冲突处理、ASL计算