学习笔记

虚拟化的目标是让每个进程以为自己独占资源。分两条线： CPU 虚拟化 → 进程（见总览章节） 内存虚拟化 → 虚拟地址空间（本章主体） 地址空间 什么是地址空间 **地址空间（Address Space）**是进程看到的内存视图： 0x…

内核在做什么 内核是唯一运行在内核态的代码。它的职责： 管理资源：进程、内存、设备、文件系统 提供抽象：把硬件包装成系统调用接口 维持秩序：调度、隔离、保护、错误处理 内核与应用程序的根本区别：内核可以直接碰硬件、可以执行特权指令、可以…

持久化解决的是：数据在程序结束、机器断电之后仍然存在。 与虚拟化和并发不同，持久化面对的核心难题是崩溃（crash）——写数据的过程中断电，磁盘上会留下一个"半写"的状态。 I/O 设备：标准模型 ┌──────────…

自动关联目录：Operating system 操作系统回答的问题是：如何在有限、杂乱、不可信的硬件之上，给应用程序提供一个简洁、安全、可复用的抽象。 它做的全部事情可以归纳为三个词：虚拟化（Virtualization）、并发（Concu…

0. 这个项目的定位 大模型工程可以拆成六个层次，每一层的"核心矛盾"都不同： 层 核心矛盾 关键指标 本项目对应 数据 质量 vs 规模 去重率、质量分分布、B/token tiniestgpt/data…

自动关联目录：Tree 树是图的一个特例：连通且无环，nnn 个点恰好 n−1n-1n−1 条边。 但它值得单独成章，因为： 递归结构天然适配分治和 DP 大量问题（文件系统、语法树、组织架构、决策树）本身就是树 图上的很多问题在树上简单…

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。 原理 最优子结构 具有最优子结构也可能是适合用贪心的方法求解。 注意要确保我们考察了最…

自动关联目录：Graph 图是表达"关系"的通用模型。很多看起来不像图的题，建出图来就迎刃而解。 术语 术语 含义 顶点 / 边 vertex / edge 有向图 / 无向图 边有没有方向 度 /…

两种遍历 DFS（深度优先） BFS（广度优先） 数据结构 栈（递归 / 显式栈） 队列 顺序 一条路走到底再回溯 一层一层扩散 找什么 路径、连通性、拓扑序 最短（少）步数 空间 O(深度)O(\text{深度…

自动关联目录：Hash 哈希（Hash）回答的是：如何用 O(1)O(1)O(1) 的代价，判断"我见过这个东西吗"。 它的代价是放弃有序性——哈希表里取不出"最小的元素"，也做不了范围查询。 需要范…

自动关联目录：Linear 线性结构是元素排成一列的结构。区别在于允许在哪些位置插入/删除。 总览 结构 插入/删除位置 访问 典型用途 数组 任意（但要搬移） O(1)O(1)O(1) 随机 默认选择 链表 已知位置 O…

自动关联目录：Misc 不属于单一主题，但到处都在用的东西。 复杂度分析 三种记号 记号 含义 类比 OOO（大 O） 上界，不超过 ≤\le≤ Ω\OmegaΩ（大 Ω） 下界，至少 ≥\ge≥ Θ\ThetaΘ（大…

四种遍历 A / \ B C / \ \ D E F 遍历 顺序 结果 先序（Preorder） 根 → 左 → 右 A B D E C F 中序（Inorder） …

自动关联目录：String 字符串问题的三个层次： 单串：在一个串里找结构（回文、周期、子串） 双串：两个串的关系（匹配、最长公共子串/子序列） 多串：一堆串的查询（Trie、AC 自动机、后缀数组） 字符串匹配 在文本 TTT（长 …

自动关联目录：Data Structures & Algorithm 这里记录的是解题方法，不是"把 STL 用熟"。核心是三类能力： 看出问题的结构（能归约到哪个模型） 选对工具（哪种数据结构/算法能支撑所需…

倍增在做什么 **倍增（Binary Lifting）**的核心思想： 预处理出"跳 2k2^k2k 步"的信息，之后任意 nnn 步都拆成二进制，用 O(log⁡n)O(\log n)O(logn) 次跳跃拼出来。 …

二分在做什么 二分的本质不是"在有序数组里找数"，而是： 在一个单调的判定函数上，用 O(log⁡n)O(\log n)O(logn) 次询问定位分界点。 把问题看成：有一个序列 [false, false, ...…

枚举在做什么 **枚举（Enumeration / Brute Force）**是最诚实的算法：把所有候选答案试一遍，取最优或计数。 复杂度通常是指数级，所以枚举不是"随便写个 for"，而是：如何高效、不重不漏地遍历答…

贪心在做什么 贪心（Greedy）：每一步都做当前看起来最优的选择，不回头。 贪心: 局部最优 → 局部最优 → ... → 全局最优（？） DP: 枚举所有选择，取全局最优 核心难点：贪心不一定对。它的正确性必须证明，不能靠&…

自动关联目录：Basic Algorithm 这一组是不依赖特定数据结构的通用算法思想。它们不是"某一类题的解法"，而是思考问题的方式——后面所有高级算法都是它们的组合。 一张表 思想 一句话 适用信号 枚…