1. 术语表¶

2-3 tree¶

一种特殊的 B 树 ，其中每个内部结点要么有 2 个子结点，要么有 3 个子结点。键值有序排列以维持 二叉搜索树性质 。2-3 树始终是高度平衡的，其插入、查找和删除操作的代价均为 \(\Theta(\log n)\) 。

80/20 rule¶

给定一个典型的应用场景，其中包含一组记录和一系列针对这些记录的查找操作，80/20 规则是一个经验观察结果，即 80% 的记录访问通常集中在 20% 的记录上。确切数值因数据集合而异，并与 引用局部性 的概念相关。

abstract data type¶

缩写为 抽象数据类型 。在某种语言中对 数据类型 的规范说明，独立于具体实现。该抽象数据类型的 接口 是依据一个 类型 以及对该类型的一组操作来定义的。每个操作的行为由其输入和输出决定。抽象数据类型并不规定*如何*实现该数据类型。这些实现细节对抽象数据类型的用户隐藏，并防止外部访问，这一概念称为 封装 。

accept¶

当 有限自动机 在字符串上执行并终止于 接受状态 时，称其接受该字符串。有限自动机被称为接受由所有使其在执行结束时处于接受状态的字符串组成的语言。

accepting state¶

有限自动机 定义的一部分是指定某些 状态 为接受状态。如果有限自动机在输入字符串上执行并在接受状态下完成计算，则称该机器 接受 该字符串。

acceptor¶

在形式语言中，任何其主要目的是判断一个字符串是被接受（被识别为属于某种语言）还是被拒绝的机器。这与计算某个值的机器形成对比。

activation record¶

程序执行期间存储在 运行时栈 上的实体。它存储任何活动的 局部变量 以及调用新子程序的返回地址，以便在子程序终止时可以恢复这些信息。

acyclic graph¶

在 图 术语中，不包含任何 环 的图。

address¶

内存中的一个位置。

adjacency list¶

一种 图 的实现，它使用（基于数组的） 线性表 来表示图的 顶点 ，而每个顶点又由一个（链接的）列表表示，该列表包含所有 邻居 的顶点。

adjacency matrix¶

一种 图 的实现，它使用一个二维 数组 ，其中每一行和每一列都对应于 图 中的一个 顶点 。矩阵中的给定行和列对应于一条从该行对应的 顶点 到该列对应的顶点的边。

adjacent¶

如果 树 的两个 结点 或 图 的两个 顶点 之间有一条 边 相连，则称它们是相邻的。如果边是从 \(a\) 指向 \(b\) 的，那么我们说 \(a\) 邻接于 \(b\) ，且 \(b\) 被 \(a\) 邻接。

ADT¶

抽象数据类型 的缩写。

adversary¶

为在 对抗论证 中使用而引入的虚构构造。

adversary argument¶

一种用于问题的 下界证明 类型，其中假设一个（虚构的）“对手”控制对算法输入的访问，并以尽可能提高任何拟议算法解决该问题成本的方式提供有关该输入的信息。只要对手给出的答案不与任何先前的答案冲突，它就允许采取任何必要措施使算法需要尽可能高的成本。

aggregate type¶

一个 数据类型 ，其 成员 包含子部分。例如，典型的数据库记录。也称为 复合类型 。

algorithm¶

解决 问题 所遵循的方法或过程。

algorithm analysis¶

术语 渐近算法分析 的非正式版本，通常用作 渐近分析 的同义词。

alias¶

另一个名称。在编程中，这通常指两个 引用 引用同一个对象。

all-pairs shortest paths problem¶

给定一个 图 ，其 权值 或 边 上带有距离，找出图中每一对顶点之间的最短路径。解决此问题的一种方法是 Floyd 算法 ，它使用了 动态规划 算法技术。

allocated¶

allocation¶

在堆内存中为对象预留内存。

alphabet¶

组成给定语言中字符串的字符或符号。

alphabet trie¶

一种用于存储可变长度字符串的 字典树 数据结构。树的 \(i\) 层对应于字符串中位置 \(i\) 的字母。根结点将根据字符串的首字母产生潜在的分支。因此，所有以 "a" 开头的字符串都将存储在树的 "a" 分支中。在第二层，这些字符串将根据第二个字母进行分支分离。

amortized analysis¶

一种 算法分析 技术，它考察一系列操作的总成本，并将该总成本分摊到整个系列上。这与将每个单独操作视为独立具有 最坏情况 成本的做法相反，后者可能导致对系列总成本高估。

amortized cost¶

用于 摊还分析 的一系列操作的总成本。

ancestor¶

在树中，对于给定结点 \(A\) ，从 \(A\) 到根的 路径 上的任何结点都是 \(A\) 的祖先。

antisymmetric¶

在集合记号中，关系 \(R\) 是反对称的，如果对于所有 \(a, b \in \mathbf{S}\) ，只要 \(aRb\) 且 \(bRa\) ，则 \(a = b\) 。

approximation algorithm¶

一种用于 优化问题 的算法，它能找到一个良好但未必最便宜的解。

arm¶

在 磁头 的上下文中，指将 I/O 磁头上的传感器固定到 吊杆 上的部件。

array¶

一个 数据类型 ，用于在连续的内存位置存储元素，并通过索引引用它们。

array-based list¶

使用 数组 存储列表元素的 线性表 抽象数据类型的一种实现。典型实现在创建列表时固定数组大小，而 空间开销 是当前未使用的数组位置数量。

array-based queue¶

类似于 基于数组的线性表 ，这在实现 队列 抽象数据类型时使用 数组 来存储元素。

array-based stack¶

类似于 基于数组的线性表 ，这在实现 栈 抽象数据类型时使用 数组 来存储元素。

ASCII character coding¶

美国信息交换标准代码。一种使用二进制代码对字符进行编码的常用方法。标准 ASCII 使用 8 位代码来表示大小写字母、数字、一些标点符号以及一些非打印字符（如回车符）。现在很大程度上已被 UTF-8 编码所取代。

assembly code¶

由 编译器 生成的一种 中间代码 形式，易于转换为计算机可执行的最终形式。汇编语言通常是将 CPU 可执行的一条或几条指令直接映射为便于人类阅读的助记符形式。

asymptotic algorithm analysis¶

渐近分析 的一个更正式的术语。

asymptotic analysis¶

一种通过识别算法或计算机程序的 增长率 来估算其效率的方法。渐近分析还提供了一种定义 问题 固有难度的方式。我们经常使用术语 算法分析 来表示相同的意思。

attribute¶

在 面向对象编程范式 中，是 数据成员 的同义词。

automata¶

有限状态机 的同义词。

automatic variable¶

局部变量 的同义词。当程序流进入和离开变量的作用域时，自动变量会自动分配和释放。

average case¶

在 算法分析 中，给定输入规模 \(n\) 的所有 问题实例 的成本的平均值。如果并非所有问题实例发生的概率都相等，则必须使用加权平均来计算平均情况。

average seek time¶

在 磁盘驱动器 上执行一次 寻道 操作的期望（平均）时间，假设磁头移动是在两条随机选择的磁道之间进行的。这是磁盘驱动器厂商通常提供的两项磁盘性能指标之一，另一项是 道间寻道时间 。

AVL Tree¶

二叉搜索树 的一种变体实现，与标准二叉搜索树的不同之处在于，它使用修改后的插入和删除方法来保持树的 平衡性 。类似于 伸展树 ，它在插入和删除操作中使用了 旋转 的概念。

B$^*$-tree¶

B+ 树 的一种变体。 \(\mathrm{B}^*\) 树与 \(\mathrm{B}^+\) 树相同，只是用于拆分和合并结点的规则不同。 \(\mathrm{B}^*\) 树在结点溢出时不会将其一分为二，而是尽可能地将部分记录分配给其相邻的兄弟结点。如果兄弟结点也已满，则这两个结点会拆分成三个结点。类似地，当结点下溢时，它会与其两个兄弟结点合并，并将总数减少为两个结点。因此，结点始终至少填充了三分之二。

B$^+$-tree¶

最常见的 B 树 实现形式。B$^+$-树不在 内部结点 存储数据，而仅将 查找键 的值作为在树中查找时的方向指示器。只有 叶结点 存储指向实际数据记录的 引用 。

B-tree¶

一种用于 索引 大量记录的方法。B 树是一种 平衡树 ，通常具有很高的分支因子（每个 内部结点 常多达 100 个 子结点 ），使得树非常浅。当存储在磁盘上时，结点大小被选为与所需的 I/O 单位相同（即磁盘 扇区 大小的某个倍数）。这使得只需很少的 磁盘访问 就能轻松访问树中给定 查找键 所关联的记录。B 树最常见的实现变体是 B+ 树 。

backing storage¶

在 缓存 系统或 缓冲池 的上下文中，后备存储是相对较大但较慢、需要被缓存的数据源。例如，在 虚拟内存 中，磁盘驱动器就是后备存储。在 Web 浏览器的上下文中，互联网可被视为后备存储。

backtracking¶

对解空间进行蛮力搜索的 启发式 。它本质上是解空间的 深度优先搜索 。这可以通过使用 分支限界算法 来改进。

bad reference¶

如果一个引用被分配但未初始化，则称其为坏引用。

bag¶

在集合记号中，包是一组没有顺序的元素（类似于集合），但允许存在值重复的元素（不同于集合）。

balanced tree¶

一个 树 ，其中 子树 满足某种平衡标准。两种可能性是：该树为 高度平衡 ，或者该树的每个子树中拥有大致相等数量的 结点 。

base¶

基数 的同义词。

base case¶

在 递归 或 归纳证明 中，基准情况是终止条件。这是一个简单的输入或值，无需调用递归（或使用 归纳假设 ）即可求解（或在归纳情况下得到证明）。

base class¶

在 面向对象编程范式 中，一个被另一个类 继承 的类。执行继承的类称为 子类 。

base type¶

集合中元素的 数据类型 。例如，该集合可能由整数值 3、5 和 7 组成。在此示例中，基类型是整数。

basic operation¶

基本操作的示例包括将数据项插入数据结构、从数据结构中删除一个 数据项 ，以及查找指定的 数据项 。

best case¶

在算法分析中，最好情况是指对于给定输入规模 \(n\) 的所有问题实例中成本最低的 问题实例 。请注意，最好情况**并非**指 \(n\) 很小，因为我们指的是某一类输入中的最佳情况（即，我们想要的是规模为 \(n\) 的那些输入中的最佳情况）。

best fit¶

在 内存管理器 中，最佳适配是一种 启发式 ，用于决定从 内存池 分配内存时使用哪个 空闲块 。最佳适配总是从足够大以满足内存请求的最小 空闲块 进行分配。其理由是，这种方法最能保留那些为异常大的请求所需的大块内存。其缺点是，它往往会导致以小型、不可用内存块形式出现的 外部碎片 。

BFS¶

广度优先搜索 的缩写。

big-Oh notation¶

在 算法分析 中，这是一种用于描述 上界 的简写记号，适用于某个 算法 或 问题 。

binary insertion sort¶

插入排序 的一种变体，其中通过二分查找定位待插入值的位置，然后将其放置到位。在常规使用中，由于在 数组 中移动大量元素的开销，这并不能改进标准的插入排序。但如果比较的代价远高于移动元素的代价，它在实践中很有用；或者如果我们只关心计算比较的代价，它在理论上很有用。

binary relation¶

在集合论中，一个 关系 由一组二元 元组 定义。

binary search¶

一种用于在有序列表中查找具有给定 查找键 值的 记录 的标准 递归 算法。它的运行时间为 \(O(\log n)\) 。在每一步中，查看当前子列表的中间位置，并丢弃那些键过小或过大的半数记录。

binary search tree¶

一种二叉树，对其结点值施加如下约束：对于任意结点 \(A\) ，其 查找键 值必须大于 \(A\) 左 子树 中所有结点的键值，且小于 \(A\) 右子树中所有结点的键值。若允许存在多个具有相同键值的结点，则必须采用某种约定，通常要求将这些结点置于右子树中。

binary search tree property¶

键 值在 结点 的 二叉搜索树 中的定义关系。所有存储在键值为 \(K\) 的结点的左子树中的结点，其键值均小于或等于 \(K\) 。所有存储在键值为 \(K\) 的结点的右子树中的结点，其键值均大于 \(K\) 。

binary tree¶

一个有限的结点集合，它或者为空，或者由一个根结点以及称为左、右 子树 的两棵二叉树构成，这两棵子树彼此 不相交 ，且与 根结点 不相交。

binary trie¶

一个 二叉树 ，其结构为 字典树 。通常这是 查找树 的一种实现。这意味着 查找键 值被视为二进制数字，其中与该结点在树中的 层 位置对应的数字若为"0"则表示左分支，若为"1"则表示右分支。示例包括 哈夫曼编码树 和 二叉空间分割树 。

binning¶

在 散列 中，分桶是一种 散列函数 。假设我们给定的键范围是 0 到 999，并且有一个大小为 10 的散列表。在这种情况下，一个可能的散列函数可以简单地将键值除以 100。因此，所有范围在 0 到 99 的键都会散列到槽位 0，键 100 到 199 会散列到槽位 1，依此类推。换句话说，这个散列函数将前 100 个键“分桶”到第一个槽位，接下来的 100 个键到第二个槽位，依此类推。这种方法往往使得散列函数依赖于键高位比特的分布。

binomial tree¶

高度为 \(m\) 的二项树有 \(2^m\) 个结点。它要么是一个单独的结点（如果 \(m=0\) ），要么是由两棵高度为 \(m-1\) 的二项树组成，其中一棵树的根成为另一棵树的子结点。

Binsort¶

一种排序方法，其工作原理是将每条记录根据其值放入一个桶中。然后按顺序收集这些桶以完成列表排序。这种形式通常不实用，但它是 基数排序 的概念基础。

bintree¶

一种以二进制 字典树 形式表示的 空间数据结构 ，通常用于存储二维或更高维空间中的点数据。它与 PR 四叉树 类似，不同之处在于每一层仅将一个维度平分。由于 PR 四叉树的许多叶结点不包含任何数据点，其实现常利用 享元 设计模式 。

bitmap¶

bit vector¶

一个 数组 ，它在每个位置存储一个位。通常这些位表示与一组对象关联的 布尔变量 ，使得第 \(i\) 个位是第 \(i\) 个对象的布尔值。

block¶

存储单元，通常指 磁盘驱动器 或其他 外围存储 设备上的存储。块是该设备 I/O 的基本单位。

Boolean expression¶

布尔表达式由 布尔变量 组成，并使用运算符 AND（ \(\cdot\) ）、OR（ \(+\) ）和 NOT（要否定布尔变量 \(x\) ，我们写作 \(\overline{x}\) ）。

Boolean variable¶

取值为 True 或 False 之一的变量。

boom¶

在 磁头 的上下文中，是所有 I/O 磁头连接到的中心结构。因此，它们在 寻道 操作期间一起移动。

bounding box¶

边界框（通常与参考系的坐标轴对齐）是包含一个（可能复杂的）对象的矩形区域。在图形学和计算几何中，复杂对象可能会关联一个边界框，供用于在特定位置查找对象的算法使用。其思想是：如果边界框不在感兴趣区域内，那么该对象也不在。检查边界框比检查对象本身更廉价，但仍需要一定时间。因此，如果足够多的对象并不位于感兴趣区域之外，这种方法将无法节省时间。但如果大多数对象都位于感兴趣区域之外，那么先检查边界框可以节省大量时间。

branch-and-bounds algorithm¶

回溯 的一种变体，适用于 优化问题 。我们像回溯法一样遍历 解树 。在解树中深入通常会产生额外开销。我们记录迄今为止找到的最优代价解。如果树中当前分支的代价超过了迄今为止找到的最优巡回代价，那么我们就知道应停止探索该分支。此时我们可以立即回退并选择另一条分支。

breadth-first search¶

一种 图 遍历 算法。顾名思义，在访问任何更远的结点之前，某个 结点 的所有直接 邻居 都会被 已访问 。BFS 由一个 队列 驱动。起始顶点被放入队列。然后，只要队列不为空，就从队列中取出一个结点，访问它，接着将其任何 未访问 邻居放入队列。

break-even point¶

当两个成本作为某个变量的函数进行衡量时，它们变得相等的点。特别是，用于比较两种实现的空间需求。例如，在比较 基于数组的线性表 实现与 链表 实现的空间需求时，关键问题是列表的填充程度与其容量限制（对于数组）相比如何。两种表示法具有相同空间成本的点即为盈亏平衡点。当列表超过此点变得更满时，数组实现变得更加节省空间；而当列表低于此点变得较空时，链表实现变得更加节省空间。

BST¶

二叉搜索树 的缩写。

bubble sort¶

一种简单的排序算法，在 最好情况、平均情况 和 最坏情况 下都需要 \(Theta(n^2)\) 时间。即使是优化版本，通常也运行得比 插入排序 慢，因此它没有什么可取之处。

bucket¶

在 桶散列 中，桶是 散列表 中被分组在一起的 槽位 序列。

bucket hashing¶

一种 散列 方法，其中 散列表 的多个 槽位 被分组在一起形成一个 桶 。然后，该 散列函数 要么散列到某个桶，要么以正常方式散列到 起始槽位 ，但该起始槽属于某个桶的一部分。 冲突解决 的处理首先尝试在与起始槽相同的桶内找到一个空闲位置。如果桶已满，则将该记录放入 溢出桶 中。

bucket sort¶

桶排序 的一种变体，其中每个桶关联一个 键 值范围。这需要对放入每个桶中的记录进行某种排序方法。

buddy method¶

在 内存管理器 中，另一种方法是使用 空闲块链表 和 顺序适配 方法来查找合适的空闲块以响应 内存请求 。相反，内存池会根据需要被反复对半分割成更小的块，直到达到大于或等于内存请求大小的最小 2 的幂。该名称源于这样一个事实：相同大小的相邻块的起始位置的二进制表示仅相差一位。这些块被称为“伙伴”，如果两者都空闲，它们将被合并在一起。

buffer¶

一块内存，通常位于 主存 。缓冲区的大小通常是每次访问 辅存 （例如 磁盘驱动器 ）时读取或写入的基本 I/O 单元的一倍或其倍数。

buffer passing¶

一种为 缓冲池 实现 抽象数据类型 的方法，其中在客户端与缓冲区池之间传递一个指向 缓冲区 的指针。这与 消息传递 方法形成对比，它最可能用于长消息或当消息大小始终等于缓冲区大小的情况，例如在实现 B 树 时。

buffer pool¶

一个或多个 缓冲区 的集合。缓冲池是 缓存 的一个示例。它存储在 主存 中，并保存预计在不久的将来使用的数据。当请求某个数据值时，首先搜索缓冲池。如果在缓冲池中找到了该值，则无需访问 辅存 。如果未在缓冲池中找到该值，则必须从辅助存储中获取。为了决定在需要存储新数据时将哪些数据 刷新 出缓冲池，已经开发了许多传统的 启发式方法 ，例如 最近最少使用 。

buffering¶

缓存 的同义词。更具体地说，它指的是一种安排，其中对数据的所有访问（例如在 外围存储 设备上）必须以某个最小存储单位的倍数进行。在 磁盘驱动器 上，这种基本或最小的 I/O 单位是 扇区 。之所以称为“缓冲”，是因为此类访问返回的数据块被存储在 缓冲区 中。

caching¶

将选定数据保留在 主存 中的概念。其目标是让主存中包含近期最可能被使用的数据值。缓存技术的一个例子是使用 缓冲池 。

call stack¶

也称为执行栈。一种存储函数调用序列及每个函数返回地址的栈。

Cartesian product¶

对于集合，这是 笛卡尔积 的另一个名称。

ceiling¶

写作 \(\lceil x \rceil\) ，对于实数值 \(x\) ，向上取整是最小整数 \(\geq x\) 。

child¶

在树中，由结点 \(R\) 直接指向的 结点 集合是 \(R\) 的 子结点 。

circular first fit¶

在 内存管理器 中，循环首次拟合适用于决定从 内存池 分配内存时使用哪个 空闲块 ，它是一种 启发式 。循环首次拟合是对 首次适配 内存分配的微小改进，它会记录最后分配的空闲块，并从该位置开始搜索下一个合适的空闲块。与首次拟合一样，它的优势在于通常无需查看空闲块线性表上的所有空闲块即可找到合适的空闲块。此外，相较于首次拟合，它还能将内存分配均匀地分布在整个 空闲块链表 上，这有助于最小化 外部碎片 。

circular list¶

一种 线性表 抽象数据类型实现变体，其中线性表的最后一个元素提供对线性表第一个元素的访问。

class¶

在 面向对象编程范式 中，抽象数据类型及其实现共同构成一个类。程序中类的实例化称为 对象 。

class hierarchy¶

在 面向对象编程范式 中，是一组类及其相互关系。其中一个类是 基类 ，其余的是 子类 ，它们直接或间接地从基类 继承 。

clause¶

在 布尔表达式 中，子句是一个或多个 字面量 通过 OR 连接而成。

client¶

服务的使用者。例如，调用 内存管理器 类的对象或程序部分就是该内存管理器的客户端。同样，调用 缓冲池 的类或代码也是如此。

clique¶

在 图 术语中，团是一个 子图 ，定义为图的 顶点 的任意 子集 \(U\) ，使得 \(U\) 中的每个顶点都与 \(U\) 中的其他每个顶点有一条 边 。团的大小是团中顶点的数量。

closed¶

如果一个集合在某个（二元）运算下是封闭的，那么当该运算作用于该集合的两个成员时，结果仍是该集合的一个成员。

closed hash system¶

一种 散列系统 ，其中所有记录都存储在 散列表 的槽中。这与 开散列系统 形成对比。

closed-form solution¶

一个代数方程，其值与 求和 或 递推关系 相同。将求和或递推关系替换为其闭式解的过程称为求解该求和或递推关系。

cluster¶

在 文件处理 中，一组物理上相邻的 扇区 ，它们定义了磁盘文件允许分配的最小空间单位。要求空间必须按扇区的倍数进行分配的理念是，这将减少存储文件所需的 范围 数量，从而减少处理一系列文件 磁盘访问 时预期的 寻道 操作次数。大簇大小的缺点是会增大 内部碎片 ，因为最后一个簇中未被文件实际使用的任何空间都会被浪费。

code generation¶

代码生成是 编译器 中的一个阶段，它将 中间代码 转换为代码的最终可执行形式。更广义地说，这可以指将语法分析树（用于确定程序结构的正确性）转换为计算机实际可执行的指令的过程。

code optimization¶

在 编译器 的一个阶段，对代码（通常是 汇编代码 ）进行更改，目的是用执行相同计算但运行更快的代码版本来替换它。

cohesion¶

在 面向对象编程范式 中，该术语指类具有单一明确角色或职责的程度。

Collatz sequence¶

对于给定的整数值 \(n\) ，通过对 \(n\) 执行以下计算所得到的数字序列

while (n > 1)
  if (ODD(n))
    n = 3 * n + 1;
  else
    n = n / 2;

这个问题之所以著名，是因为尽管对你尝试的任何 \(n\) 值它都会终止，但它总是终止这一事实从未被证明。

collision¶

在 散列系统 中，这指的是两个搜索 键 被 散列函数 映射到 散列表 中同一个槽位的情况。这可能发生在插入或查找时，此时已有另一条记录被散列到该槽位。在这种情况下， 闭散列系统 将需要一个称为 冲突解决 的过程来找到目标记录的位置。

collision resolution¶

一个 冲突解决策略 的结果。

collision resolution policy¶

在 散列 中，解决 冲突 的过程。具体而言，在 闭散列系统 中，这是在一个 散列表 中寻找包含所需记录的正确位置的过程，前提是 散列函数 由于与另一条记录发生 冲突 而未返回该记录的正确位置。

comparable¶

两个对象可以相互比较以确定它们是否相等，或者确定哪一个更大的概念。在集合记号中，如果对于给定关系 \(R\) ，集合的元素 \(x\) 和 \(y\) 满足 \(xRy\) 或 \(yRx\) ，则它们是可比的。为了可靠地比较大小关系，被比较的值必须属于一个 全序 。在编程中，这是数据类型的一种属性，使得该类型的两个元素可以比较以确定它们是否相同（较弱的版本），或者确定两者中哪一个更大（较强的版本）。 Comparable 也是 Java 中的一个 接口 的名称，它断言具有某个类的对象之间存在可比关系，而 .compareTo() 是实现该类两个对象之间实际比较的 Comparable 接口方法。

comparator¶

作为库方法参数（或 C++ 模板、Java 泛型参数）传入的函数。比较器函数概念提供了一种通用方式，封装了对特定类型两个对象进行比较的过程。例如，若要编写一个能处理任意记录类型的通用排序例程，可要求排序例程的使用者传入一个比较器函数，以定义集合中记录的比较方式。

comparison¶

比较两个 键 或 记录 的行为。对于许多 数据类型 ，一次比较具有常数时间代价。所需的比较次数常被用作排序和查找算法的 成本度量 。

compile-time polymorphism¶

一种称为重载的 多态 形式。重载方法具有相同的名称，但签名与类中其他位置可用的方法不同。请与 运行时多态 比较。

compiler¶

一个读取计算机程序并将其转换为可由某种形式的计算机直接执行的形式的计算机程序。编译器的主要阶段包括 词法分析 、 语法分析 、 中间代码生成 、 代码优化 和 代码生成 。更广泛地说，编译器可以被视为 解析器 程序以验证其语法正确性，然后执行 代码生成 将高级程序转换为计算机可执行的内容。

complete binary tree¶

一种二叉树，其结点逐行填充，且最底层从左到右填充。由于这一要求，对于任意 \(n\) 值，仅存在一棵包含 \(n\) 个结点的树。由于按行顺序将记录存储在 数组 中可实现从结点在数组中的位置到其 父结点 、 兄弟结点 和 子结点 的简单映射，因此数组表示法最常用于实现完全二叉树。 堆 数据结构是一种对结点值施加偏序约束的完全二叉树。

complete graph¶

一个 图 ，其中每个 顶点 都连接到其他所有顶点。

complex number¶

在数学中，复数是指同时具有实部和虚部的数。

Composite design pattern¶

给定一个表示一组对象的类层次结构，以及一个用于对象集合的容器，组合 设计模式 处理对象层次结构与对象上的一系列行为之间的关系。在组合设计中，每个对象都需要实现这一系列行为。这与过程式方法形成对比，后者将行为（例如树 遍历 ）实现为对象集合（例如 树 ）上的一个方法。过程式树遍历要求树具备一种方法，该方法能够理解当遇到树可能包含的任何对象类型（ 内部的 或 叶结点 ）时该做什么。组合方法则会让树在其根结点上调用“遍历”方法，该根结点知道如何执行“遍历”行为。这反过来可能需要调用其他对象的遍历方法（在本例中，即根结点的子结点）。

composite type¶

一种其 成员 具有子部分的数据类型。例如，典型的数据库记录。另一个术语是 聚合类型 。

composition¶

基于使用而非 继承 的类之间的关系，即 HAS-A 关系。例如，类 'A' 中的某些代码拥有指向其他类 'B' 的 引用 。

computability¶

计算机科学的一个分支，研究通过计算解决问题的理论。更具体地说，它研究哪些问题（函数）是可计算的极限。一个著名的原则上无法由计算机解决的问题的例子是 停机问题 。

computation¶

在 有限自动机 中，计算是为某个长度 \(n \geq 0\) 的一系列 配置 。一般而言，它是机器执行的一系列操作。

computational complexity theory¶

理论计算机科学和数学中计算理论的一个分支，专注于根据计算问题的固有难度对其进行分类，并将这些类别相互关联。一个例子是对 NP 完全 问题的研究。

configuration¶

对于一台 有限自动机 ，针对某个输入字符串的机器当前状态的完整描述。这包括机器当前所处的 状态 ，以及字符串的当前状态，包括即将处理的字符。

Conjunctive Normal Form¶

CNF¶

一个 布尔表达式 被写为一系列进行与运算的 子句 。

connected component¶

在 无向图 中， 结点 的一个 子集 ，使得该子集中的每个结点都可以从该子集中的任何其他结点到达。

connected graph¶

如果从任意 顶点 到任何其他结点都至少存在一条路径，则 无向图 是一个连通图。

constant running time¶

运行时间与输入规模无关的函数的代价。在 Theta 记号中，这通常写作 \(\Theta(1)\) 。

constructive induction¶

一种用于寻找 递推关系 的 闭式解 的过程，涉及将猜测的闭式代入以替换递推关系中的递归部分。根据目标（通常是证明假设的增长率正确，或找出精确的常数），随后对得到的非递归方程进行变换。

container¶

container class¶

一个 数据结构 ，用于存储一组 记录 。典型示例包括 数组 、 查找树 和 散列表 。

context-free grammar¶

一个 文法 仅由形式为 \(A \rightarrow x\) 的产生式组成，其中 \(A\) 是一个 非终结符 ，而 \(x\) 是一个或多个 终结符 和非终结符的序列。也就是说，给定的非终结符 \(A\) 可以在任何时候被替换。

context-free language¶

CFL¶

可由 上下文有关文法 定义的 语言 集合。

context-sensitive grammar¶

CFG¶

一个 文法 仅由形式为 \(xAy \rightarrow xvy\) 的产生式组成，其中 \(A\) 是一个 非终结符 ，而 \(x\) 和 \(y\) 各自是一个或多个 终结符 与非终结符的序列。也就是说，给定的非终结符 \(A\) 只有在处于合适的上下文中时才能被替换。

cost¶

解决方案所消耗的资源量。

cost model¶

在 算法分析 中，定义了算法执行的每个 基本操作 的代价以及输入规模的定义。有了这些定义，我们就可以计算在给定输入上运行算法的 成本 ，并由此确定算法的 增长率 。如果一个代价模型能够产生符合我们对现实理解的预测，那么它就可以被认为是“好”的。

countably infinite¶

countable¶

如果 集合 包含有限个元素，或者（对于包含无限个元素的集合）存在从该集合到整数集的一一映射，则它是可数无限的。

CPU¶

中央处理单元的缩写，是计算机的主要处理设备。

current position¶

某些线性表抽象数据类型的一种属性，其中维护了一个“当前位置”状态，以便后续引用。

cycle¶

在 图 术语中， 环 是一条长度至少为三的 路径 ，它将某个 顶点 \(v_1\) 连接到其自身。

cylinder¶

一个 磁盘驱动器 通常由一组 盘片 构成。虽然如今情况可能并非完全如此，但传统上所有 磁头 在一次 寻道 操作中会同步移动。因此，当某个 I/O 磁头定位到盘片上的特定 磁道 时，其他 I/O 磁头也同时定位到各自盘片上对应的磁道。这组磁道称为柱面。一个给定的柱面代表了无需再次执行寻道操作即可从所有盘片读取的全部数据。

cylinder index¶

在 索引顺序存取方法 系统中，一个简单的 线性索引 存储了每个 柱面 中保存的最小键值。

cylinder overflow¶

在 索引顺序存取方法 系统中，这是为存储无法放入各自 柱面 的任何记录而预留的空间。

DAG¶

有向无环图 的缩写。

data field¶

在 面向对象编程范式 中，是 数据成员 的同义词。

data item¶

从某种数据类型中取值的一条信息或一条记录。

data member¶

共同定义数据项所需空间的变量称为数据成员。一些常用的同义词包括 数据域 、 属性 和 实例变量 。

data structure¶

抽象数据类型 的实现。

data type¶

一种数据类型及其用于操作该类型的一组操作。

deallocated¶

deallocation¶

释放分配给未使用对象的内存。

debugging¶

一旦确定程序未按预期运行，对其进行修正。这与 测试 形成对比。

decideability¶

在 可计算性 理论中，研究的是一个问题是否可以被回答。一个典型的例子是判断系统中的两个实例是否等价。“两个计算机程序是否做相同的事情？”是 停机问题 的一个变体（且不可判定）。“两个 确定有限自动机 是否做相同的事情？”是可判定的。

decision problem¶

输出为“是”或“否”的问题。

decision tree¶

用于建模算法行为的理论构造。算法做出决策的每个点（例如 if 语句）都由表示算法行为的树中的一个分支来建模。决策树可用于 下界证明 ，例如证明在 最坏情况 中排序需要 \(\Omega(n \log n)\) 次比较。

deep copy¶

复制 被指向对象 的实际内容。

degree¶

在 图 术语中， 顶点 的度是其 邻居 的数量。在 有向图 中， 入度 是指向该顶点的边的数量，而 出度 是从该顶点指出的边的数量。在 树 术语中， 结点 的度是其 子结点 的数量。

delegation mental model for recursion¶

一种思考 递归 过程的方式。递归函数在进行递归调用时“委托”了大部分工作。这种用于递归的委托思维模型的优势在于，你无需考虑被委托的任务是如何执行的，它自然会被完成。

dense graph¶

一个 图 ，其中 边 的实际数量占可能边数的很大比例。通常，这意味着图中任意 顶点 的 度 相对较高。

depth¶

树中结点 \(M\) 的深度是从树的根结点到 \(M\) 的路径长度。

depth-first search¶

一个 图 遍历 算法。每当在遍历过程中遇到一个 \(v\) 被 已访问 时，深度优先搜索将 递归地 访问 \(v\) 的所有 未访问 邻居 。

depth-first search tree¶

一个 树 ，可以通过在 图 上执行 深度优先搜索 （深度优先查找）来定义。这棵树将由图的 结点 以及在深度优先查找过程中所经过的图的 边 的一个子集组成。

dequeue¶

用于表示从队列中移除一个元素的专用术语。

dereference¶

访问某个 引用 变量的 被指向对象 的值。通常，这在像 Java 这样的语言中发生，当使用“点”运算符来访问对象的某个字段时。

derivation¶

在形式语言中，从 文法 执行一系列 产生式规则 的过程。推导的一个典型例子是从 开始符号 到给定字符串所执行的一系列产生式。

descendant¶

在树中，所有以结点 \(A\) 为 祖先 的结点集合是 \(A\) 的后代。换句话说，所有这些结点都可以从 \(A\) 出发，沿着树向下到达。另一种说法是： \(A\) 的 子结点 、它们的子结点，依此类推。

deserialization¶

将数据结构的 序列化的 表示还原为其原始内存形式的过程。

design pattern¶

用于描述程序设计（即对象与类的交互）的抽象概念。经验丰富的软件设计师会学习并复用组合软件组件的模式，而设计模式使得这种设计知识能够更快地传递给新程序员。

deterministic¶

任何 有限自动机 ，其中对于每一对 状态 和符号，仅存在一个转移。这意味着每当机器处于给定状态并看到给定符号时，只会发生一件事。这与 非确定的 有限自动机形成对比，后者至少有一个状态在至少一个符号上具有多个转移。

deterministic algorithm¶

不涉及任何随机性元素的算法，因此其在给定输入上的行为始终相同。这与 随机化算法 形成对比。

Deterministic Finite Automata¶

Deterministic Finite Acceptor¶

DFA¶

一个 自动机 或抽象机器，可以从左到右处理输入字符串（显示在磁带上）。它有一个控制单元（具有 状态 ），定义了当处于给定状态且磁带当前方格上为给定符号时应执行的行为。我们所能“做”的只是在移向右侧下一个字母之前改变状态。

DFS¶

深度优先搜索 的缩写。

diagonalization argument¶

一种用于证明某个集合为 不可数无穷 的证明技术。其方法是表明，无论该集合的元素以何种顺序排列，总能构造出一个不在该排序中的新元素。这是通过修改元素的第 \(i\) 个值或位置，使其与所提议排序中第 \(i\) 个元素的对应值不同来实现的。

diameter¶

对于 无向图 ，这是任意一对顶点之间的最长路径。使用 Floyd 算法 是计算此值的好方法。

dictionary¶

抽象数据类型或 接口 是一种用于数据结构或软件子系统的接口，支持记录的插入、查找和删除操作。

dictionary search¶

插值查找 的近亲。在自然语言单词的经典（纸质）词典中，会有标记指示以给定字母开头的单词在词典中的起始位置。因此，在使用此类词典的典型场景中，查找单词的方法是翻到包含该字母开头单词的页面范围内的适当位置。

digraph¶

有向图 的缩写。

Dijkstra's algorithm¶

求解 单源最短路径问题 中 图 的算法。这是一个 贪心算法 。它与查找 最小成本生成树 的 Prim 算法 几乎完全相同，唯一的区别在于更新已知最短距离时所执行的计算。

diminishing increment sort¶

希尔排序 的另一个名称。

direct access¶

一种存储设备，例如磁盘驱动器，具有或多或少直接移动到所需数据位置的能力。这与 顺序访问 存储设备（如磁带驱动器）形成对比。

direct proof¶

一般来说，直接证明只是一种“逻辑解释”。直接证明有时也被称为演绎论证。这只是基于逻辑的论证。它通常用英语书写，使用诸如“如果……那么”之类的词语，也可以用逻辑记号书写，例如 \(P \Rightarrow Q\) 。

directed acyclic graph¶

一个 图 且无环。缩写为 有向无环图 。注意，DAG 不一定是 树 ，因为给定的 结点 可能拥有多个 父结点 。

directed edge¶

一条从一个 顶点 指向另一个顶点的 边 。相比之下， 无向边 只是无方向地连接两个顶点。

directed graph¶

一个 图 ，其每个 边 均从一个定义它的 顶点 指向另一个。

dirty bit¶

在 缓冲池 中，与每个 缓冲区 关联的一条信息用于指示自其从 后备存储 读入以来缓冲区的内容是否已发生变化。当缓冲区从缓冲区池 已刷新 时，若脏位被设置（即内容已改变），则必须将缓冲区内容写入后备存储。这意味着需要执行一次相对昂贵的写操作。相反，如果脏位未被设置，则无需将内容写入后备存储，从而比不跟踪内容是否变化节省了时间。

Discrete Fourier Transform¶

DFT¶

设 \(a = [a_0, a_1, ..., a_{n-1}]^T\) 为一个向量，用于存储待求值多项式的系数。随后，我们可以通过将 \(A_{z}\) 矩阵乘以系数向量，来计算该多项式在 \(n\) 个 \(roots of unity <nth roots of unit>\) 处的值。所得向量 \(F_{z}\) 称为该多项式的离散傅里叶变换（或 DFT）。

discriminator¶

多维查找键 的一部分。某些树数据结构，如 二叉空间分割树 和 kd 树 ，其工作原理是在树的结点处根据多维键的单个属性进行分支决策，该属性由结点在树中的层级决定。例如，在 2 维情况下，树中奇数层的结点可能根据坐标的 \(x\) 值进行分支，而偶数层则根据坐标的 \(y\) 值进行分支。因此， \(x\) 坐标是奇数层的判别器，而 \(y\) 坐标是偶数层的判别器。

disjoint¶

数据结构 的两个部分，或两个没有公共对象的集合，是不相交的。该术语常与具有 结点 的数据结构（如 树 ）一起使用。也用于 集合 的上下文中，其中如果两个 子集 没有共享元素，则它们是不相交的。

disjoint sets¶

一组 集合 ，其中任意两个集合都没有公共元素。不相交集合的集合对某些对象进行划分，使得每个对象恰好属于其中一个不相交集合。

disk access¶

从磁盘驱动器（或其他形式的 外围存储 ）读取数据的行为。对于涉及磁盘 I/O 的算法，数据必须从磁盘读取（或写入）的次数通常是衡量其成本的良好指标，因为这通常是主要成本。

disk controller¶

磁盘驱动器 的控制机制。负责读取或写入 扇区 数据的操作。

disk drive¶

是 外围存储 或 辅存 的一个例子。数据访问时间通常以千分之一秒（毫秒）计，这大约比 RAM 的访问时间慢一百万倍，而 RAM 是 主存 设备的一个例子。对磁盘驱动器的读写总是以某个最小尺寸为单位进行，这个最小尺寸通常称为 块 。在大多数磁盘驱动器上，块大小为 512 字节。磁盘驱动器和 RAM 是计算机 存储层次结构 的典型组成部分。

disk I/O¶

指从 磁盘驱动器 读取数据或向其写入数据的操作。所有磁盘读写均以 扇区 或 块 为单位进行。

disk-based space/time tradeoff¶

与标准 时空权衡 相反，该原则指出：磁盘存储需求越小，程序运行速度越快。这是因为从磁盘读取信息的时间相对于计算时间而言极其巨大，因此几乎任何为解包数据所需的额外计算量，都会小于因减少存储需求而节省的磁盘读取时间。

distance¶

在 图 表示中， 权值 的同义词。

divide and conquer¶

一种设计算法的技术，通过将问题分解为更小（相似）的子问题、求解这些子问题，然后合并子问题的解以形成原问题的解。该过程通常使用 递归 实现。

divide-and-conquer recurrences¶

递推关系 的一种常见形式具有如下形式

\[{\bf T}(n) = a{\bf T}(n/b) + cn^k; \quad {\bf T}(1) = c\]

其中 \(a\)、\(b\)、\(c\) 和 \(k\) 均为常数。 一般来说，这个递推关系描述的是一个规模为 \(n\) 的问题， 它被分解为 \(a\) 个规模为 \(n/b\) 的子问题， 而 \(cn^k\) 则是将这些子问题的解 合并起来所需的工作量。

divide-and-guess¶

一种为 求和 或 递推关系 寻找 闭式解 的技术。

domain¶

函数的可能输入集合。

double buffering¶

使用多个 缓冲区 以使 中央处理器 能够与 外围存储 设备并行运行的思想。一旦第一个缓冲区的数据被读入，CPU 就可以在处理这些数据的同时从外围存储设备读取下一块数据。要使这一思想奏效，必须能够以合理的准确度知晓或预测待处理的下一块数据。

double hashing¶

一种 冲突解决 方法。第二个散列函数用于为键生成一个值 \(c\) 。然后，该键使用该值作为 步进线性探测 中的步长。由于不同的键使用不同的步长（由第二个散列函数生成），此过程避免了标准按步线性探测所导致的聚集。

double rotation¶

一种由 伸展树 和 AVL树 使用的 重平衡操作 类型。

doubly linked list¶

一种 链表 实现变体，其中每个链表结点都包含指向列表中前一个元素和后一个元素的访问指针。

DSA¶

数据结构与算法的缩写。

dynamic¶

会变化的事物（与 静态的 相对）。在计算机编程中，动态通常指在运行时发生的事情。例如，运行时分析是对程序行为的分析，而不是对其（静态）文本或结构的分析。动态绑定或动态内存分配发生在运行时。

dynamic allocation¶

从 自由存储区 创建对象的行为。在 C++、Java 和 JavaScript 中，这是通过 new 运算符完成的。

dynamic array¶

数组一旦分配，其大小即固定。动态数组在数组周围放置一个 接口 ，使其看起来能够根据需要增长或缩小。通常的做法是分配一个新的副本，复制旧数组的内容，然后将旧数组返回给 自由存储区 。如果操作正确，动态调整数组大小的 摊还成本 可以设为常数。在某些编程语言（如 Java）中，术语 向量 被用作动态数组的同义词。

dynamic memory allocation¶

一种编程技术，其中数据结构中的链接对象按需从 自由存储区 创建。当不再需要时，该对象要么返回到 自由存储区 ，要么作为 垃圾 保留，具体取决于编程语言。

dynamic programming¶

一种通过存储子问题结果表来设计算法的方法。 递归的 算法中成本过高的典型原因是递归的不同分支可能求解相同的子问题。动态规划使用一张表来存储哪些子问题已被求解的信息，并利用该存储信息立即给出任何重复尝试求解该子问题的答案。

edge¶

连接 树 、 链表 或 图 中两个 结点 的链接。

edit distance¶

给定字符串 \(S\) 和 \(T\) ，编辑距离是将 \(S\) 转换为 \(T\) 所需的编辑步骤数的度量。

efficient¶

如果一个解法能在所需的 资源约束 内解决问题，则称该解法是高效的。有时，如果一个解法比已知的替代方案需要更少的资源，无论其是否满足任何特定要求，也称该解法是高效的。

element¶

集合中的一个值或成员。

empirical comparison¶

一种通过实际观察性能来比较事物的方法。通常，我们指的是通过在测试数据集上运行两个程序并测量其实际运行时间来进行比较。经验比较可能受到许多潜在复杂因素的影响，包括测试数据的不公平选择，以及由于程序在不同执行过程中计算环境的变化而导致的时间测量不准确。

empty¶

对于 容器 类，其状态为不包含任何 元素 。

encapsulation¶

在编程中，封装是指向抽象数据类型的用户隐藏实现细节的概念，并保护对象的 数据成员 免受外部访问。

enqueue¶

用于表示将元素插入队列的专用术语。

entry-sequenced file¶

按记录添加到文件中的顺序存储记录的文件。

enumeration¶

遍历 列出 容器 中每个结点恰好一次的过程。因此，打印 结点 的遍历被称为枚举结点。枚举也可以指由遍历产生的实际列表（以及创建该列表的过程）。

equidistribution property¶

在随机数理论中，这意味着给定的一系列随机数无法被比直接列出它们更简洁地描述。

equivalence class¶

一个 等价关系 可用于将集合划分为等价类。

equivalence relation¶

关系 \(R\) 是集合 \(\mathbf{S}\) 上的等价关系，如果它是 自反 、 对称 和 传递 。

equivalent¶

在形式语言的研究中，如果两个实体接受相同的语言，则它们是等价的。也就是说，如果 \(L(M_1) = L(M_2)\) ，则实体 \(M_1\) 和 \(M_2\) 是等价的。如果两种用于表示或识别语言的机制所接受的语言集合相同，则它们是等价的。例如， 确定有限自动机 和 非确定有限自动机 是等价的，因为每个 DFA 在技术上都是 NFA，并且每个 NFA 都可以转换为 DFA。

estimation¶

作为一项技术技能，这是生成粗略估计以评估所提出解决方案可行性的过程。这有时被称为“餐巾纸背面”或“信封背面”计算。估计过程可以形式化为：(1) 确定影响问题的主要参数，(2) 推导将参数与问题关联起来的方程，然后 (3) 为参数选择值并应用该方程以得出估计解。

evaluation¶

在给定位置计算多项式值的操作。

exact-match query¶

查找键值与指定键值完全匹配的记录。这与 范围查询 形成对比。

exceptions¶

异常是用于预测可能的运行时错误并妥善处理它们的技术。

exchange¶

在 数组 中交换相邻记录。

exchange sort¶

一种仅依靠交换（相邻记录的互换）来重排线性表的排序。 插入排序 和 冒泡排序 是交换排序的示例。所有交换排序在 最坏情况 下都需要 \(\Theta(n^2)\) 时间。

expanding the recurrence¶

一种求解 递推关系 的技术。其思想是用递推式的副本替换递推式中的递归部分。

exponential growth rate¶

一个 增长率 函数，其中 \(n\) （输入规模）出现在指数中。例如， \(2^n\) 。

expression tree¶

一个 树 结构，用于表示数学表达式。表达式树的 内部结点 是表达式中的运算符，其子树是作为操作数的子表达式。所有 叶结点 都是操作数。

extent¶

磁盘文件中的一块物理上连续的 扇区 ，它们都位于同一个 磁盘驱动器 上。存储磁盘文件数据所需的区段越少，通常处理该文件上一系列 磁盘访问 操作所需的 寻道 操作也就越少。

external fragmentation¶

当一系列 内存请求 导致产生大量微小的 空闲块 ，而其中任何一个都无法用于服务典型请求时，就会出现这种情况。

external sort¶

一种应用于存储在 外围存储 中的数据（例如在 磁盘驱动器 上）的排序算法。这与作用于存储在 主存 中的数据的 内部排序 形成对比。

factorial¶

阶乘函数定义为 \(f(n) = n f(n-1)\) 对应 \(n > 0\) 。

failure policy¶

在 内存管理器 中，失败策略是指当无法从 内存池 的当前 空闲块 满足 内存请求 时所采取的响应。可能的做法包括拒绝请求、扩展内存池、收集 垃圾 ，以及重组内存池（以合并空闲空间）。

family of languages¶

给定某个 有限自动机 类或类型（例如 确定有限自动机 ），该类有限自动机所接受的语言集合称为一个族。例如， 正则语言 是由 DFA 定义的一个族。

FIFO¶

“先进先出”的缩写。这是 队列 的访问范式，队列的旧术语是"FIFO 线性表”。

file allocation table¶

一种最初为 DOS 开发并随后在 Windows 中使用的旧式文件系统架构。它仍用于许多小型外围设备，例如 U 盘和数码相机存储。

file manager¶

操作系统 中负责接收来自 逻辑文件 的数据请求，并将这些请求映射到磁盘上数据物理位置的部分。

file processing¶

计算机科学中处理存储在 磁盘驱动器 （文件中）的数据，或更广泛地说，处理存储在任何 外围存储 设备上的数据的领域。两个基本特性使得处理外围设备上的数据与处理内存中的数据不同：(1) 在外围存储设备上读取/写入数据远比在内存中读取/写入数据慢得多（例如，典型的磁盘驱动器比 随机存取存储器 慢约一百万倍）。(2) 对外围设备的所有 I/O 操作通常以数据 块 为单位进行（例如，几乎所有磁盘驱动器都以 512 字节的块为单位进行所有 I/O 操作）。

file structure¶

数据在 外围存储 上的组织方式，例如 磁盘驱动器 或 DVD 驱动器。

final state¶

任何 接受器 的必需元素。当对字符串的计算在终态结束时，机器接受该字符串；否则机器拒绝该字符串。

FIND¶

管理 不相交集合 的 合并/查找 算法的一半。它是在树中向上移动以找到树的根结点的过程。

Finite State Acceptor¶

一种简单的 有限状态自动机 类型，接受器的唯一能力是接受或拒绝一个字符串。因此，有限状态接受器不具备修改输入带的能力。如果对该字符串的计算最终停在 终态 ，则该字符串被接受，否则被拒绝。

Finite State Machine¶

FSM¶

Finite State Automata¶

FSA¶

Finite Automata¶

任何抽象状态机，通常表示为一个图，其中结点是 状态 ，边表示当机器处于该结点（状态）并看到适当输入时发生的结点间转换。例如，参见 确定有限自动机 。

first fit¶

在 内存管理器 中，首次适配是一种 启发式 ，用于决定从 内存池 分配内存时使用哪个 空闲块 。首次适配总是分配 空闲块链表 上第一个足够大以满足内存请求的 空闲块 。这种方法的优势在于，通常无需查看空闲块链表上的所有空闲块即可找到合适的空闲块。其缺点在于，它并未“智能地”选择可能更优的空闲块。

fixed-length coding¶

给定一组对象，固定长度编码方案使用长度相同的代码为集合中的每个对象分配一个代码。字符的标准 ASCII 和 Unicode 表示都是固定长度编码方案的示例。这与 变长编码 形成对比。

floor¶

写作 \(\lfloor x \rfloor\) ，对于实数值 \(x\) ，向下取整是最大整数 \(\leq x\) 。

Floyd's algorithm¶

一种解决 全点对最短路径问题 的算法。它使用了 动态规划 算法技术，并在 \(\Theta(n^3)\) 时间内运行。与任何 动态规划 算法一样，关键问题是通过适当记录算法在解空间中的进展来避免重复工作。基本思想是首先找到所有直接边代价，然后通过允许经过 顶点 0 的路径来改进这些代价，接着是涉及经过顶点 0 和 1 的最便宜路径，依此类推。

flush¶

从 缓存 中移除数据的操作，通常是因为其他被认为具有更高未来价值的数据必须在缓存中替换它。如果被刷出的数据自从从 辅存 首次读入后已被修改（且这些更改需要保存），则必须将其写回该辅助存储。在 缓冲池 的上下文中，当需要 缓冲区 来存储新数据时，移除其中所存内容的过程。如果缓冲区的内容自从从 后备存储 读入后已发生更改（这一事实通常通过使用 脏位 来跟踪），则在重用该缓冲区之前，必须将它们复制回后备存储。

flyweight¶

一个 设计模式 旨在解决以下问题：你有一个包含许多对象的应用程序。其中一些对象在它们所包含的信息以及所扮演的角色上是相同的。但是必须从各个位置访问它们，并且概念上它们确实是不同的对象。由于存在大量相同信息的重复，我们希望通过共享该空间来降低内存成本。例如，在文档排版中，字母"C"可能由一个描述该字符笔画和边界框的对象表示。然而，我们不希望在文档中每次出现"C"的地方都创建一个单独的"C"对象。解决方案是为"C"对象分配共享表示形式的单个副本。然后，文档中每个需要在给定字体、大小和字形中使用"C"的位置都将引用这个单一副本。指向特定形式"C"的各种 引用 实例称为享元。享元也可用于实现 二叉空间分割树 和 PR 四叉树 的空叶结点。

folding method¶

在 散列 中，实现 散列函数 的一种方法。当键为字符串时最常使用，折叠法将字符串拆分为若干段（也许每个字母为一段，或一小串字母为一段），将字母转换为整数值（通常使用其底层编码值），然后将各段求和。

Ford and Johnson sort¶

一种接近排序所需理论最小键比较次数的排序算法。由于需要移动的记录数量较多而导致效率不高，因此在实践中通常被认为不实用。该算法首先将结点两两配对并根据比较结果分为胜者和败者，然后（递归地）对胜者进行排序，最后精心选择将败者加入已排序链的顺序。

forest¶

一个或多个 树 的集合。

free block¶

内存池 中一块未使用的空间。

free block list¶

在 内存管理器 中，存储有关当前 空闲块 必要信息的线性表。通常，这是通过某种 链表 完成的，其中链表的每个结点指示 内存池 中空闲块的起始位置和长度。

free store¶

程序在运行时可用于 动态分配 对象的空间。自由存储区不同于 运行时栈 。自由存储区有时被称为 堆 ，这可能会引起混淆，因为 堆 更常指代一种特定的数据结构。大多数编程语言都提供函数来从自由存储区分配（以及可能释放）对象，例如 C++ 和 Java 中的 new 。

free tree¶

一个连通的、 无向图 且无简单环的图。等价的定义是：自由树是连通的，并且有 \(|\mathbf{V}| - 1\) 条边。

freelist¶

一种简单且更快的替代方案，用于在动态分配的对象大小相同（因此可互换）时取代 自由存储区 。通常实现为 链式栈 ，释放的对象会被放入空闲线性表的表头。当请求分配对象时，首先检查空闲线性表，若可能则由其提供对象。如果空闲线性表为空，则从 自由存储区 分配新对象。

frequency count¶

一种 启发式 用于维护一个 自组织线性表 。在此启发式规则下，每条记录都维护一个计数。当访问一条记录时，其计数增加。如果这使得它的计数大于列表中另一条记录的计数，则它相应地向列表前端移动，以保持列表按频率排序。这类似于用于维护 缓冲池 的 最不经常使用 启发式规则。

full binary tree theorem¶

该定理指出，非空满二叉树中叶结点的数量比内部结点的数量多一个。等价地，标准 二叉树 中空指针的数量比二叉树中结点的数量多一个。

full tree¶

一棵 二叉树 是满的，如果每个 结点 要么是 叶结点 ，要么是拥有两个非空 子结点 的 内部结点 。

function¶

在数学中，匹配是输入（ 定义域 ）与输出（ 值域 ）之间的对应关系。在编程中，函数是一个子程序，它接收输入参数，利用这些参数计算并返回一个值。在这种情况下，通常认为函数修改任何全局变量是不好的做法（这样做称为副作用）。

garbage¶

在 内存管理器 中，任何在运行时由程序（动态）分配但不再可访问的内存，因为所有指向该内存的指针都已被删除或覆盖。在某些语言中，垃圾可以通过 垃圾回收 回收。在像 C 和 C++ 这样不支持垃圾收集的语言中，产生垃圾被视为一种 内存泄漏 。

garbage collection¶

具有垃圾回收机制的语言（如 Java、JavaScript、Lisp 和 Scheme）会定期回收 垃圾 并将其返回到 自由存储区 。

general tree¶

一种树，其中任意给定结点可以拥有任意数量的 子结点 。这与例如 二叉树 形成对比，后者中每个结点拥有固定数量的子结点（其中一些可能为 null ）。正因如此，一般树的结点往往更难实现。

grammar¶

以一组 产生式规则 来定义哪些字符串构成 语言 的形式化定义。

graph¶

一个 图 \(\mathbf{G} = (\mathbf{V}, \mathbf{E})\) 由一组 顶点 \(\mathbf{V}\) 和一组 边 \(\mathbf{E}\) 组成，使得 \(\mathbf{E}\) 中的每条边都是 \(\mathbf{V}\) 中一对顶点之间的连接。

greedy algorithm¶

一种在每一步都做出局部最优选择的算法。

growth rate¶

在 算法分析 中， 算法 的成本随其输入规模增长而增长的速率。

guess-and-test¶

一种用于确定 闭式解 对于 求和 或 递推关系 的技术。给定一个关于闭式解的假设，如果它是正确的，那么通常使用 归纳 来证明它相对容易。

guided traversal¶

一个 遍历 ，它无需访问树中的每个结点。例如，在 二叉搜索树 中进行 范围查询 。

halt state¶

在 有限自动机 中，存在一个指定的 状态 ，当进入该状态时会导致机器立即停止。

halted configuration¶

当机器进入 停机状态 时，会在 图灵机 中发生停机配置。

halting problem¶

停机问题是要回答这个问题：给定一个计算机程序 \(P\) 和一个输入 \(I\) ，程序 \(P\) 在输入 \(I\) 上执行时是否会停止？该问题已被证明在一般情况下无法解决。因此，它是 不可解问题 的一个例子。

handle¶

当使用 内存管理器 存储数据时， 客户端 会将待存储的数据（即 消息 ）传递给内存管理器，而内存管理器会向客户端返回一个句柄。该句柄编码了内存管理器日后用于恢复消息并将其返回给客户端所需的信息。这通常是消息在 内存池 中的位置和长度。

hanging configuration¶

当 I/O 磁头从磁带最左侧的方格向左移动，或者机器进入无限循环时， 图灵机 中会出现挂起配置。

happy path testing¶

测试程序的“正确”输入或用法。

hard algorithm¶

在计算机科学理论中，“难”传统上是根据运行时间来定义的，而“难”算法被定义为具有指数运行时间的算法。

hard problem¶

在计算机科学理论中，“难”传统上是根据运行时间来定义的，而一个“难”问题被定义为已知最佳算法需要指数级运行时间的问题。

harmonic series¶

从 1 到 \(n\) 的倒数之和称为调和级数，记作 \({\cal H}_n\) 。该和的值介于 \(\log_e n\) 与 \(\log_e n + 1\) 之间。

hash function¶

在 散列系统 中，该函数将 键 值转换为 散列表 中的一个位置。希望散列表中的该位置包含与键值匹配的记录。

hash system¶

基于散列查找的搜索实现在 散列表 中。 查找键 由 散列函数 处理，它返回 散列表 中的一个位置，希望该位置就是找到与查找键对应记录的正确位置。

hash table¶

用于存储数据记录以便通过 散列 进行查找的数据结构（通常是一个 数组 ）。

hashing¶

一种搜索方法，它使用 散列函数 将 查找键 值转换为 散列表 内的位置。在正确实现的 散列系统 中，该表中的位置有很高的概率包含与键值匹配的记录。有时，由于称为 冲突 的过程，散列函数会返回一个未存储所需键的位置。在这种情况下，需要通过称为 冲突解决 的过程来找到所需的记录。

head¶

一个 线性表 的开始。

header node¶

常用于 链表 或相关结构的实现中，此 结点 位于线性表的第一个元素之前。其目的是通过减少必须编程处理的特殊情况数量来简化代码实现。

heap¶

该术语有两种不同的含义。不常见的是，它是 自由存储区 的同义词。最常见的是，它用于指代一种特定的数据结构。这种数据结构是一棵 完全二叉树 ，要求每个 结点 的值都大于其 子结点 （称为 最大堆 ），或者要求每个结点的值都小于其子结点（称为 最小堆 ）。由于它是一棵完全二叉树，堆几乎总是使用 数组 来实现，而不是使用显式的树结构。向堆中添加一个新值，或移除极值（大顶堆中的最大值或小顶堆中的最小值）并更新堆，在 最坏情况 下需要 \(\Theta(\log n)\) 时间。然而，如果给定一个无序数组中的所有值，则可以在仅 \(\Theta(n)\) 时间内重新排列这些值以形成堆。由于其空间和时间效率，堆是实现 优先队列 的流行选择。

heapsort¶

一种在 最好情况 、 平均情况 和 最坏情况 情况下时间成本为 \(\Theta(n \log n)\) 的排序算法。它往往比 归并排序 和 快速排序 慢。它通过构建一个 最大堆 ，然后反复移除具有最大 键 值的项（将其移动到堆的末尾），直到所有元素都被移除（并替换到数组中的适当位置）。

height¶

树的高度是树中最深 结点 的 深度 。

height balanced¶

指树中每个 子树 的 深度 都大致相同的条件。

heuristic¶

一种解决问题的方法，不能保证是最优解。虽然不能保证最优，但通常预期（由使用该启发式的代理）能提供一个相当高效的解。

heuristic algorithm¶

一种 近似算法 ，它使用 启发式 来寻找 优化问题 的一个良好但未必最便宜的解。

home position¶

在 散列 中，是 起始槽位 的同义词。

home slot¶

在 散列 中，这是由 散列函数 为给定键确定的 散列表 中的 槽位 。

homogeneity¶

在 容器 类中，这一性质要求存储在容器中的所有对象都属于同一个类。例如，如果你有一个旨在存储工资记录的线性表，程序员是否可能将一个整数插入到该线性表中？

Huffman codes¶

通过哈夫曼编码过程分配给一组字母（或其他符号）的编码。哈夫曼编码使用 哈夫曼编码树 来生成这些编码。这些编码可以是可变长度的，使得预期出现频率最高的字母具有更短的编码。只要真实频率已知，且字母的频率独立于其在消息中的上下文，哈夫曼编码就是最优的。

Huffman coding tree¶

Huffman 编码树是一种 满树 ，用于高效地表示字母（或其他符号）。每个字母与树中的一个结点相关联，并根据该关联结点的位置被赋予一个 哈夫曼编码 。Huffman 编码树是二叉 字典树 的一个示例。

Huffman tree¶

术语 哈夫曼编码树 的简写形式。

I/O head¶

在 磁盘驱动器 （或类似设备）上，实际从磁盘读取数据的机械部件。

image-space decomposition¶

一种 键空间分解 形式，其中 键空间 分割点是预先确定的（通常通过平分实现）。例如，一个 哈夫曼编码树 将被编码的字母分为左侧代码以 0 开头的和右侧代码以 1 开头的两组。这种对键空间的规则分解是 字典树 数据结构的基础。图像空间分解与 对象空间分解 相对立。

in degree¶

在 图 术语中， 顶点 的入度是指指向该顶点的边的数量。

incident¶

在 图 术语中，连接两个顶点的边称为与这些顶点关联。这两个顶点称为 相邻 。

index file¶

一种文件，其记录由 键值对 组成，其中指针引用存储在另一个文件中的完整记录。

indexing¶

将 查找键 与相应数据记录的位置相关联的过程。索引概念的两个定义要点是：将键与记录关联，以及索引并不实际存储记录本身，而是存储指向该记录的 引用 。通过这种方式，一组记录可以由多个索引支持，通常为记录中的每个键字段设置一个独立的索引。

induction hypothesis¶

在 归纳证明 中使用的关键假设是，待证明的定理对较小规模的实例成立。归纳假设等价于递归函数中的 递归的 调用。

induction step¶

归纳证明 的一部分。在其最简单的形式中，这是对如下蕴含关系的证明：如果该定理对 $n-1$ 成立，则它对 $n$ 也成立。另一种方法见 强归纳 。

induction variable¶

用于参数化通过归纳法证明的定理的变量。例如，如果我们试图证明从 1 到 $n$ 的整数之和为 $n(n+1)/2$，则 $n$ 是归纳变量。归纳变量必须是整数。

information theoretic lower bound¶

基于唯一指定答案所需的信息位数，对解决 问题 所需资源量的 下界 。由于香农在信息论和熵方面的工作，有时也被称为“香农理论下界”。一个例子是，排序的下界为 \(\Omega(\log_2 n!)\) ，因为对于 \(n\) 个值有 \(n!\) 种可能的排列顺序。仅凭这一观察并不能使该下界变得紧致，因为有可能没有任何算法能够实际达到信息论的下限。

inherit¶

在 面向对象编程范式 中，一个 子类 从 基类 获取 数据成员 和 方法 的过程。

initial state¶

起始状态 的同义词。

inode¶

“索引结点”的简称。在 UNIX 风格文件系统中，指存储定义文件系统布局的索引信息的特定磁盘块 扇区 。

inorder traversal¶

在 二叉树 中， 遍历 首先 递归地 访问 左 子结点 ，然后访问 根结点 ，接着递归访问右子结点。在 二叉搜索树 中，这种遍历将按排序顺序 枚举 各结点。

Insertion Sort¶

一种排序算法，其 最坏情况 和 平均情况 代价为 \(\Theta(n^2)\) ，而 最好情况 代价为 \(Theta(n)\) 。这种最好情况代价使得当有理由预期输入几乎有序时，该算法非常有用。

instance variable¶

在 面向对象编程范式 中，是 数据成员 的同义词。

integer function¶

输入与输出均为整数的函数。可以通过 对角化论证 证明，整数函数的集合是 不可数无穷 。

inter-sector gap¶

在磁盘驱动器上，数据中位于 扇区 之间的物理间隙。这使得 磁头 能够检测到扇区的结束。

interface¶

接口是一种类似类的结构，仅包含方法签名和字段。接口不包含方法的实现或任何 数据成员 。

intermediate code¶

典型 编译器 的一个步骤是将原始高级语言转换为更易于执行该过程其他阶段的形式。例如，某些编译器会将原始高级源代码转换为 汇编代码 ，以便在其上执行 代码优化 ，然后再将其翻译为最终的可执行形式。

intermediate code generation¶

编译器 中的一个阶段，遍历 分析树 以生成简单的 汇编代码 。

internal fragmentation¶

当为 \(m\) 字节的 内存请求 分配超过 \(m\) 字节时发生的一种情况，这会浪费空闲存储空间。这通常是为了简化 内存管理器 。

internal node¶

在树中，任何拥有至少一个非空 子结点 的结点都是内部结点。

internal sort¶

一种应用于存储在 主存 中的数据的排序算法。这与旨在处理存储在 外围存储 （例如在 磁盘驱动器 上）的数据的 外部排序 形成对比。

interpolation¶

给定某些点处的值，求多项式系数的过程。一个 \(n-1\) 次多项式需要 \(n\) 个点来插值其系数。

interpolation search¶

给定一个已排序的数组，并已知存储在某个包含 查找键 \(K\) 的子数组中的第一个和最后一个 键 值，插值查找将计算 \(K\) 在该子数组中的预期位置，表示为已知键值之间距离的一个分数。因此，它接下来将检查该计算出的位置，从而缩小下一次迭代的查找范围。在合理的键值分布下，插值查找的 平均情况 将为 \(\Theta(\log \log n)\) ，优于 二分查找 的预期代价。尽管如此，由于两种代价之间的差异很小，加之实现插值查找相比二分查找需要更高的常数因子，因此在几乎所有实际情况下，二分查找预计会更快。

interpreter¶

与将高级程序翻译成可重复执行以进行计算的 编译器 不同，解释器直接对高级语言执行计算。这往往使得计算速度比在编译器生成的可直接执行版本上进行的计算慢得多。

inversion¶

衡量一系列值无序程度的指标。对于序列中的每个元素 \(X\) ，其左侧每个值大于 \(X\) 的元素都相对 \(X\) 构成一次逆序（因此在排序过程中这些元素最终必须被移动到 \(X\) 的右侧）。

inverted file¶

当倒排表存储在磁盘文件中时， 倒排表 的同义词。

inverted list¶

一个 索引 ，它将 次键 链接到关联的 主键 或数据库中的实际记录。

irreflexive¶

在集合记号中，集合 \(S\) 上的二元关系 \(R\) 如果对于任何 \(a \in \mathbf{S}\) ， \(aRa\) 都不在该关系中，则称其为反自反的。

ISAM¶

索引顺序访问方法：一种过时的数据索引方法，用于（在当时）快速检索。更广义地说，该术语也泛指支持对数据记录进行顺序和 键 访问的 索引 。如今，这几乎总是使用 B 树 来实现。

iterator¶

在 容器 （如线性表）中，有一个独立的类用于指示容器内的位置，并支持对容器中所有 元素 进行 遍历 。

job¶

操作系统要运行的进程或任务的常用名称。它们通常需要按重要性顺序处理，因此由 优先队列 组织。该术语的另一个常见用途是指由 拓扑排序 排序的任务集合。

jump search¶

一种用于查找有序线性表的算法，其计算成本与概念复杂度介于 顺序查找 和 二分查找 之间。其思路是按某个固定位置数不断跳跃，直到找到一个大于 查找键 \(K\) 的值，然后在已知包含查找键的子数组上执行顺序查找。对于大小为 \(n\) 的数组，最优跳跃步数为 \(\sqrt{n}\) ，且 最坏情况 成本为 \(\Theta(\sqrt{n})\) 。

K-ary tree¶

一种 满树 ，其中每个内部结点恰好有 \(K\) 个 子结点 。

k-path¶

在 Floyd 算法 中，k-路径是连接两个顶点 \(i\) 和 \(j\) 的路径，且该路径只能经过索引值小于或等于 \(k\) 的顶点。

kd tree¶

一种使用二叉树根据数据记录在空间中的（点）位置来存储这些数据记录的 空间数据结构 。它在每一层使用一个 判别符 的概念，以决定在该层依据 多维查找键 的哪一个单一分量进行分支。它采用 键空间分解 ，这意味着结点左子树中的所有数据记录在对应判别器上的值均小于该结点的值，而右子树中的所有数据记录则具有更大的值。 二叉空间分割树 是 kd 树的 图像空间分解 类比。

key¶

用于在查找或比较时代表该记录的一个字段或较大记录的一部分。 查找键 的另一种说法。

key sort¶

任何应用于 键值对 集合的排序操作，其中此处的值是一个 引用 ，指向完整记录（即内存中记录的指针或磁盘上记录的位置）。这与直接作用于记录集合的排序操作形成对比。其意图是，键集合远小于记录本身的集合。因此，当直接对记录排序需要 外部排序 时，这可能允许使用 内部排序 。键集合还可以充当 索引 。

key space¶

键 值可能取值的范围。

key-space decomposition¶

将 查找键 的范围划分为若干片段的想法。对此有两种通用方法： 对象空间分解 和 图像空间分解 。

key-value pair¶

解决如何在特定 索引 上下文中将 键 值与记录关联（或如何为给定记录查找键）这一问题的标准方案是：在索引中直接存储由键和记录组成的对作为记录。具体而言，索引通常会存储键的副本以及指向该记录的 引用 。解决此问题的另一种标准方案是向索引传递一个 比较器 函数。

knapsack problem¶

尽管该问题有许多变体，但这里是一个典型版本：给定一个固定大小的背包和一组尺寸各异的对象，是否存在一个对象子集能恰好装入该背包？已知该问题是 NP 完全 ，但可以使用 动态规划 在相对较短的实际时间内求解问题实例。因此，它被认为具有 伪多项式 代价。 优化问题 版本则是寻找能够装入最多数量物品的子集，既可以按它们的总尺寸衡量，也可以按与每个物品关联的价值之和来衡量。

Kruskal's algorithm¶

用于计算 最小成本生成树 的 图 算法。在处理过程中，它利用 合并/查找 过程来高效地确定两个顶点是否位于同一个 子图 中。

labeled graph¶

一个 图 ，其标签与 结点 相关联。

language¶

可以从给定 字母表 生成的字符串的一个子集。

Las Vegas algorithms¶

随机化算法 的一种形式。我们总能找到最大值，并且“通常”能很快找到。这类算法能保证得到结果，但不保证运行时间短。

leaf node¶

在 二叉树 中，叶结点是任何拥有两个空 子结点 的结点。（注意，二叉树的定义要求每个结点都有两个孩子，这就是为什么叶结点必须有两个空孩子，而不是没有孩子。）在树中，任何没有孩子的结点都是叶结点。

least frequently used¶

简写为 LFU ，它是一种 启发式 ，用于决定当缓冲池中的数据必须被读入 缓存 的新数据替换时，应 刷新 缓冲池 中的哪个 缓冲区 。不过， 最近最少使用 比 LFU 更流行。类似于维护 自组织线性表 的 频率计数 启发式方法。

least recently used¶

简写为 最近最少使用 ，它是一种流行的 启发式 ，用于决定当缓冲池中的数据必须被读入 缓存 的新数据替换时，应 刷新 缓冲池 中的哪个 缓冲区 。类似于维护 自组织线性表 的 移至前端 启发式方法。

left recursive¶

在自动机理论中，如果 产生式 具有 \(A \rightarrow Ax\) 、 \(A \in V, x \in (V \cup T)^*\) 的形式，则称其为左递归的，其中 \(V\) 是 文法 中 非终结符 的集合，而 \(T\) 是 终结符 的集合。

length¶

在 线性表 中，指元素的数量。在字符串中，指字符的数量。

level¶

在树中，所有 深度 \(d\) 的结点都位于树的第 \(d\) 层。根结点是唯一位于第 0 层的结点，其深度为 0。

lexical analysis¶

负责读取程序或语言的字符并将它们分组为 记号 的 编译器 或 解释器 阶段。

lexical scoping¶

在编程语言中，仅允许在定义该变量的代码块内访问该变量的约定。这是 静态作用域 的同义词。

LFU¶

最不经常使用 的缩写。

lifetime¶

对于变量，生命周期是指其在被销毁之前存在的时间长度。

LIFO¶

“后进先出”的缩写。这是 栈 的访问范式，栈的旧术语是"LIFO 线性表”。

linear congruential method¶

在随机数理论中，一种用于计算 伪随机 序列中下一个数的过程。从 种子 开始，序列中的下一项 \(r(i)\) 通过方程由第 \(r(i-1)\) 项计算得出

\[r(i) = (r(i-1)\times b) \bmod t\]

其中 \(b\) 和 \(t\) 是常数。 这些常数必须经过精心选择，才能使 生成的数列具有作为随机数序列的理想性质。

linear growth rate¶

对于输入规模 \(n\) ，增长率为 \(cn\) （其中 \(c\) 为任意正常数）。换句话说，相关函数的成本与输入规模呈线性关系。

linear index¶

一种 索引 形式，它将 键值对 存储在有序数组中。通常，这用于磁盘上存储的大量记录的索引，其中线性索引本身可能位于磁盘或 主存 中。它允许高效查找（包括 范围查询 ），但不适合在数组中插入和删除条目。因此，当系统需要执行范围查询且一旦创建线性索引后记录集合永不改变时，它是一种理想的索引结构。

linear order¶

全序 的另一个术语。

linear probing¶

在 散列 中，这是最简单的 冲突解决 方法。 探测序列 的项 \(i\) 就是 \(i\) ，这意味着冲突解决通过从 起始槽位 开始依次遍历散列表来实现。虽然简单，但它效率低下，因为它很快会导致散列表中的某些空闲 槽位 在插入或查找过程中被选中的概率更高。

linear probing by steps¶

在 散列 中，此 冲突解决 方法是简单 线性探测 的一种变体。定义某个常数 \(c\) ，使得 探测序列 的第 \(i\) 项为 \(ci\) 。这意味着冲突解决通过从 起始槽位 开始以 \(c\) 为步长在散列表中顺序移动来实现。虽然它对线性探测改进不大，但它构成了另一种称为 双重散列 的冲突解决方法的基础，其中每个键使用由第二个 散列函数 定义的 \(c\) 值。

linear search¶

顺序查找 的另一个名称。

link node¶

一种广泛使用的支持对象，构成 链表 及类似 数据结构 的基本构建块。链接结点包含一个或多个用于存储数据的字段，以及指向另一个链接结点的 指针 或 引用 。

linked list¶

使用 动态分配 的 链接结点 来存储列表元素的线性表抽象数据类型实现。常见变体包括 单链表 、 双向链表 和 循环链表 。所需的 空间开销 是每个链接结点中的指针。

linked stack¶

类似于 链表 ，在实现栈抽象数据类型时使用 动态分配 的结点来存储元素。

list¶

一个有限的、有序的 数据项 序列，称为 元素 。这接近于数学中的 序列 概念。注意，此定义中的“有序”意味着列表元素具有位置。它并不指列表元素的 键 值之间的关系（即，“有序”并不意味着“已排序”）。

literal¶

在 布尔表达式 中， 字面量 是一个 布尔变量 或其否定。在编译器的上下文中，它是任何常数值。类似于 终结符 。

load factor¶

在 散列 中，这是包含记录的 散列表 槽位 的比例。散列系统通常试图将负载因子保持在 50% 以下。

local storage¶

局部存储。

local variable¶

在函数或方法中声明的变量。它仅存在于从函数被调用到函数退出的时间段内。当函数被挂起（由于调用另一个函数）时，该函数的局部变量存储在 活动记录 上的 运行时栈 中。

locality of reference¶

访问记录集合时分布不均匀的概念。这可能表现为少量记录承受了大部分访问（ 80/20 规则 ）。或者，它可能表现为下一次或未来的访问靠近最近一次访问的概率增加。这是 缓存 成功的基本属性。

logarithm¶

值 \(y\) 以 \(b\) 为底的对数是 \(b\) 需要提升到多少次幂才能得到 \(y\) 。

logical file¶

在 文件处理 中，程序员将存储在 磁盘驱动器 上的 随机访问 文件视为连续的字节序列，这些字节可能组合形成数据记录。这与 物理文件 形成对比。

logical form¶

从抽象数据类型的角度定义数据类型。与数据类型的 物理形式 进行对比。

lookup table¶

一张预先计算好的值表，用于在这些值被多次访问时加快处理速度。这种方法的代价是存储该表所需的空间以及计算该表所需的时间。这是 时空权衡 的一个例子。

lower bound¶

在 算法分析 中，一个 增长率 始终小于或等于所讨论 算法 的增长率。在实践中，这是我们所知的增长最快的函数，它除了对常数数量的输入外，增长速度都不超过所有其他情况。它可能是对真实值的一个严重低估。由于算法的下界在不同情况下（例如 最好情况 或 最坏情况 ）可能差异很大，我们通常需要指明所指的具体情况。

lower bounds proof¶

关于下界的证明，该术语通常指解决给定 问题 的任何可能算法的下界。许多问题都有一个简单的下界，其基于最小处理量与查看问题的所有输入相关这一概念。然而，有些问题的下界高于此值。例如，排序问题（ \(\Omega(n \log n)\) ）的下界大于排序的输入规模（ \(n\) ）。证明此类问题的“非平凡”下界是出了名的困难。

LRU¶

最近最少使用 的缩写。

main memory¶

主存 的同义词。在计算机中，这通常是 随机存取存储器 。

map¶

一个将 键 与 记录 关联起来的 数据结构 。

mapping¶

一个 函数 ，它将给定 集合 的每个元素映射到另一个集合中的唯一元素；一种对应关系。

mark array¶

在许多 图 算法中，通常需要跟踪在算法执行过程中哪些结点已被访问过。为此，通常会维护一个由位或值组成的 数组 ，称为 标记数组 。

mark/sweep algorithm¶

一种用于 垃圾回收 的算法。所有可访问的变量，以及从任何可访问变量通过指针链可达的任何空间，均被“标记”。然后对内存池中的所有内存进行一次顺序扫描。任何未标记的内存位置都被视为程序不再需要，并可作为空闲空间予以重用。

master theorem¶

一个使求解 分治递归式 变得容易的定理。

matching¶

在图论中，图中各种结点的配对（或匹配）。

matching problem¶

任何涉及在图中寻找具有某种期望性质的 匹配 的问题。例如，一个众所周知的 NP 完全 问题是为无向图寻找一个 最大匹配 。

max heap¶

一个 堆 ，其中每个 结点 的 键 值都大于其 子结点 。因此，具有最大键值的结点位于 根结点 。

maximal match¶

在图中，指任何不留下一对相连的未匹配顶点的 匹配 。极大匹配不一定是 最大匹配 。换句话说，可能存在比已找到的极大匹配更大的匹配。

maximum lower bound¶

在无序列表中查找最大值的 问题 的 下界 是 \(\Omega(n)\) 。

maximum match¶

在图中，最大可能的 匹配 。

MCST¶

MST¶

最小成本生成树 的缩写。

measure of cost¶

当比较两个事物（例如两种算法）时，必须使用某个事件或单位作为比较的基本单位。它可能是程序所需的毫秒数或执行的机器指令数，但通常希望有一种无需编写程序即可比较两种算法的方法。因此，可以使用其他某种成本度量作为算法之间比较的基础。例如，在比较两种排序算法时，传统上使用记录对的键值之间进行的 比较 次数作为成本度量。

member¶

在集合记号中，这是 元素 的同义词。在抽象设计中， 数据项 是 类型 的成员。在对象编程语言中， 数据成员 是对象中的数据成员。

member function¶

与抽象数据类型相关的每个操作都由一个成员函数或 方法 实现。

memory allocation¶

在 内存管理器 中，响应内存请求的行为。

memory deallocation¶

在 内存管理器 中，释放一块内存的操作应当创建或扩充一个 空闲块 。

memory hierarchy¶

计算机系统将数据存储在不同类型的存储介质中，这些介质从快速但昂贵（ 主存 ）到缓慢但廉价（ 辅存 ）不等。当数据量过大无法全部存入 主存 时，目标是通过使用 缓存 技术，尽可能将近期或最常被访问的数据保留在主存中。

memory leak¶

在编程中，创建 垃圾 的行为。在不支持 垃圾回收 的语言（如 C 和 C++）中，重复的内存泄漏最终会导致程序终止。

memory manager¶

管理 内存池 的功能。通常，内存管理器将内存池视为一个 数组 字节。内存管理器的 客户端 将请求一组（相邻的）特定大小的字节，并在不再需要该空间时释放这些字节以供重用。内存管理器不应了解客户端存入内存池的数据的任何解释含义。根据具体实现，客户端可能会传入要存储的数据，此时内存管理器将负责把数据实际复制到内存池中。内存管理器将向客户端返回一个 句柄 ，客户端稍后可使用该指针检索数据。

memory pool¶

内存（通常位于 随机存取存储器 ，但也可能在磁盘或 外围存储 设备上）在逻辑上被视为一个内存位置数组。内存池通常由 内存管理器 管理。

memory request¶

在 内存管理器 中，某个 客户端 向内存管理器发出请求，以预留一块内存并在其中存储一些字节。

merge insertion sort¶

Ford-Johnson 排序 的同义词。

Mergesort¶

一种在 最好情况、平均情况 和 最坏情况 下都需要 \(\Theta(n \log n)\) 时间的排序算法。概念上它很简单：把线性表分成两半，分别排序，再把它们归并到一起。在 数组 上高效地实现它则稍微有些复杂。

message¶

在 内存管理器 实现中（特别是采用 消息传递 风格的 接口 实现的内存管理器），消息是内存管理器的 客户端 希望存储在 内存池 中的数据。内存管理器将通过返回一个 句柄 来响应客户端，该句柄定义了消息在内存池中的存储位置和大小。客户端随后可以通过将该句柄传回给内存管理器来恢复消息。

message passing¶

实现 抽象数据类型 的一种常见方法是采用 内存管理器 或 缓冲池 ，其中待存储的 消息 内容在客户端与内存管理器之间显式传递。这与 缓冲区传递 方法形成对比。

metaphor¶

人类通过为对象或概念的集合赋予一个标签，然后操作该标签来代替操作整个集合，从而应对复杂性。认知心理学家将这种标签称为隐喻。

method¶

在 面向对象编程范式 中，方法是对 类 的操作。 成员函数 的同义词。

mid-square method¶

在 散列 中，一种实现 散列函数 的方法。将键值平方，并从结果值的中间提取若干位作为散列码。必须小心提取那些确实位于结果值中间的位，这需要了解典型键值的特性。如果操作正确，这种方法的优点是散列码会受到键所有位的影响。

min heap¶

一个 堆 ，其中每个 结点 的 键 值都小于其 子结点 。因此，具有最小键值的结点位于 根结点 。

minimal-cost spanning tree¶

缩写为 MCST，有时也缩写为 MST。它源自一个 带权图 ，MCST 是图的 边 的 子集 ，在保持图连通性的同时具有最低总成本（由 MCST 中边的 权值 之和定义）。结果被称为 树 ，因为它永远不会包含 环 （因为可以从环中移除一条边而仍然保持连通性）。解决此问题的两种算法是 Prim 算法 和 Kruskal 算法 。

minimum external path weight¶

给定一组对象，每个对象在树中关联一个 叶结点 ，具有最小外部路径权重的二叉树是对于给定叶结点集合其 加权路径长度 之和最小的那棵。这一概念用于构建 哈夫曼编码树 ，其中权重较大的字母应具有较小的深度，从而使其对总路径长度的贡献最小。因此，若另一个字母的权重较小，则它可能会被推至树的更深层。

mod¶

模 函数的缩写。

model¶

对现实的一种简化，仅保留基本要素。借助模型，我们可以更轻松地聚焦并推理这些基本要素。在 算法分析 中，我们尤其关注用于衡量算法成本的 成本模型 。

modulus¶

取模函数返回整数除法的余数。在数学表达式中有时写作 \(n \bmod m\) ，而在许多编程语言中的语法是 n % m 。

Monte Carlo algorithms¶

随机化算法 的一种形式。我们可以快速找到最大值，或者根本得不到答案（但速度很快）。虽然这类算法具有良好的运行时间，但其结果无法保证。

move-to-front¶

用于维护 自组织线性表 的 启发式 。在此启发式方法下，每当访问一条记录时，就将其移动到线性表的表头。类似于维护 缓冲池 的 最近最少使用 启发式方法。

multi-dimensional search key¶

包含多个部分的键，与 多维查找结构 协同工作。最典型的情况是， 空间的 键表示多维（2 维或 3 维）空间中的一个位置。但多维键也可用于组织非空间维度内的数据，例如温度和时间。

multi-dimensional search structure¶

一种用于支持在 多维查找键 上进行高效查找的数据结构。这里的核心理念是，多维查找结构通过将查找键的多个部分视为一个整体来工作，比针对键的每个一维分量进行独立查找更为高效。一个主要示例是 空间数据结构 ，它能够高效地表示并在多维空间中查找记录。

multilist¶

可包含子表的线性表。该术语有时用作 包 的同义词。

natural numbers¶

零和正整数。

necessary fallacy¶

在 下界证明 中，一个常见的错误是证明做出了不恰当的假设，即任何算法都必须以某种方式运行（通常是以某些已知算法的行为方式）。

neighbor¶

在 图 中，如果存在一条从 \(v\) 到 \(w\) 的 边 ，则称 结点 \(w\) 是 结点 \(v\) 的邻居。

node¶

构成链表或二叉树等链接结构的对象。通常，结点使用 动态内存分配 分配。在 图 术语中，结点更常被称为 顶点 。

non-deterministic¶

在 有限自动机 中，至少有一个 状态 对至少一个符号具有多个转移。这意味着在该情况下，关于采取哪个转移是不 确定的 的。如果一个非确定性机器在某种 接受状态 下，通过至少一种非确定性转移的选择完成了对该字符串的执行，则称该机器 接受 该字符串。通常，可以通过在每种分支选择所对应的执行之间交替运行，用确定性机器来模拟非确定性。

non-deterministic algorithm¶

一种可能使用 非确定选择 操作的算法。

non-deterministic choice¶

一种捕捉非确定性概念的操作。非确定性选择可以视为在一组选项中“正确猜测”，或者并行地实现每个选项。在并行视角下，如果至少有一个选项能导出正确答案，则非确定性成功。

non-deterministic polynomial time algorithm¶

一个在多项式时间内运行的算法，它可能（也可能不）使用 非确定选择 。

non-strict partial order¶

在集合记号中，一个关系是 自反 、 反对称 和 传递 。

non-terminal¶

与 终结符 不同，非终结符是 产生式规则 中的抽象状态。从 开始符号 开始，所有非终结符必须转换为终结符才能完成 推导 。

Nondeterministic Finite Automata¶

Nondeterministic Finite Acceptor¶

NFA¶

一个 自动机 或抽象机器，可以从左到右处理输入字符串（显示在磁带上）。它有一个控制单元（具有 状态 ），定义了当处于给定状态且磁带当前方格上为给定符号时应执行的行为。我们所能“做”的只是在移向右侧下一个字母之前改变状态。与 确定有限自动机 不同，非确定性有限自动机可能在同一输入符号下从给定状态产生多个转移，或者可能存在从给定状态在空串上的转移。

NP¶

非确定性多项式时间算法 的缩写。

NP-Complete¶

一类以这种方式相互关联的问题：如果其中任何一个问题被证明可在多项式时间内求解，或被证明需要指数时间，则所有其他 NP 完全问题的代价也将相同。由于如此多的现实世界问题已被证明是 NP 完全的，因此确定它们具有多项式代价还是指数代价将极为有用。但迄今为止，尚无人能确定这一情况的真相。更技术性的定义是：若一个问题属于 NP 且为 NP 难，则该问题是 NP 完全的。

NP-Completeness proof¶

一种用于证明特定 问题 为 NP 完全 的 归约 。具体而言，NP 完全性证明必须首先表明该问题属于 非确定性多项式时间 类，然后通过归约到另一个 NP 完全问题来证明该问题是 NP 难 。

NP-hard¶

一个与 非确定性多项式时间 中任何其他问题“一样难”的问题。也就是说，如果 NP 中的任何算法都能在多项式时间内 归约 到问题 X，则问题 X 是 NP 难的。

nth roots of unity¶

复平面中单位圆上表示 本原 n 次单位根 倍数的所有点。

object¶

类 的一个实例，即在计算机程序执行期间被创建并占用存储的东西。在 面向对象编程范式 中，对象是操作的基本单位。对象具有以 数据成员 形式存在的状态，并且知道如何执行某些动作（ 方法 ）。

object-oriented programming paradigm¶

一种问题求解方法，其中所有计算均使用 对象 完成。

object-space decomposition¶

一种 键空间分解 形式，其中 键空间 由所找到的键的实际值确定。例如，一个 二叉搜索树 在其根结点存储一个键值，而树中所有其他较小值都位于左 子树 。因此，根结点的值已根据其值将该键的键空间分割（或分解）为左部和右部。对象空间分解与 图像空间分解 相反。

octree¶

三维空间中的 四叉树 等价物是一棵具有 \(2^3\) 或八个分支的树。

Omega notation¶

在 算法分析 中， \(\Omega\) 记号用于描述一个 下界 。大致上（但不完全）类似于用于定义 上界 的 大 O 记号 。

one-way list¶

单链表 的同义词。

open addressing¶

闭散列系统 的同义词。

open hash system¶

一个 散列系统 ，其中多条记录可能与同一个 散列表 槽位关联。通常这是使用链表来存储记录的。这与 闭散列系统 形成对比。

operating system¶

计算机的控制程序。其目的是控制硬件、管理资源，并向其他软件组件提供访问这些资源的标准接口。

optimal algorithm¶

若一个算法的成本（对于给定的一类输入，如最好情况、平均情况或最坏情况）在求解该问题的下界的一个常数因子范围内，则称该算法是最优的。例如，线性搜索在未排序的数组上对所有类别的输入都是最优的。归并排序在平均情况和最坏情况下对排序是最优的，快速排序在平均情况下对排序是最优的，而插入排序在最好情况下对排序是最优的。

optimal static ordering¶

一种理论构造，用于定义放置记录集合的最佳静态（不变）顺序，以最小化通过一系列顺序查找访问的记录 已访问 数量。它是一个有用的概念，可用于定义理论最优值，以便与 自组织线性表启发式 的性能进行比较。

optimization problem¶

任何存在（通常数量庞大的）潜在解集合，且目标是找到最优解的问题。一个例子是旅行商问题，其中按某种顺序访问 \(n\) 个城市会产生代价，而目标是以最低代价的顺序进行访问。

orthogonal list¶

用于实现 稀疏矩阵 的一种数据结构。

out degree¶

在 图 术语中， 顶点 的出度是指从该顶点指出的边的数量。

overflow¶

实体中存储的数据量超过其容量时的状态。例如， B 树 中的一个结点可以存储一定数量的记录。如果尝试将一条记录插入已满的结点，则必须采取措施处理这种情况。

overflow bucket¶

在 桶散列 中，这是当包含该记录 起始槽位 的桶已满时，记录被放入的 桶 。溢出桶在逻辑上被视为具有无限容量，尽管在实践中，如果许多记录存储在溢出桶中，查找和插入操作将变得相对昂贵。

overhead¶

数据结构存储的除实际数据外的所有信息。例如， 链表 或 二叉搜索树 中的指针域，或 基于数组的线性表 中未使用的位置。

page¶

一个常用于指代 缓冲池 或其他 虚拟内存 中单个 缓冲区 内容的术语。这对应于来自 后备存储 的单个 块 或 扇区 数据，它们是 I/O 的基本单位。

parameter¶

构成 函数 输入的各个值。

parent¶

在树中，直接链接到结点 \(A\) 的 结点 \(P\) 是 \(A\) 的双亲。 \(A\) 是 \(P\) 的 子结点 。

parent pointer representation¶

对于 树 ，一种 结点 实现，其中每个结点仅存储指向其 父结点 的指针，而非指向其 子结点 。这使得沿树向上朝向 根结点 变得容易，但向下朝向 叶结点 则不然。这最适合用于解决 合并/查找 问题。

parity¶

匹配偶数性或奇数性的概念，这是使用 奇偶校验位 进行错误检测的基本思想。

parity bit¶

一种用于检查比特序列传输是否正确的常用方法。其思想是统计序列中 1 比特的数量，若该数量为奇数则将奇偶校验位设为 1，若为偶数则设为 0。随后，可检查所传输的比特序列，看其奇偶性是否与奇偶校验位的值匹配。这种方法能够检测某些类型的错误，特别是当单个比特的值发生反转时。例如，早期版本的 ASCII 字符编码 就使用了该方法。

parse tree¶

表示输入字符串语法结构的树，便于与 文法 进行比较以判断其语法是否正确。

parser¶

编译器 的一部分，它以程序文本（或更典型地，来自 扫描器 的记号）作为输入，并验证程序在语法上是否正确。通常，它会在此过程中构建一个 分析树 。

partial order¶

在集合记号中，若一个二元关系是 反对称 且 传递 ，则称其为偏序。若该关系还是 自反 ，则它是一个 非严格偏序 。或者，若该关系还是 非自反 ，则它是一个 严格偏序 。

partially ordered set¶

定义了 偏序 的集合称为偏序集。

partition¶

在 快速排序 中，将线性表划分为两个子线性表的过程，其中一个子线性表的值小于 枢轴 值，另一个子线性表的值大于枢轴。此过程在长度为 \(i\) 的子线性表上花费 \(\Theta(i)\) 时间。

pass by reference¶

变量的 引用 被传递给被调用函数。因此，任何修改都将影响原始变量。

pass by value¶

变量的副本被传递给被调用函数。因此，任何修改都不会影响原始变量。

path¶

在 树 或 图 术语中，若对于 \(1 \leq i < n\) 存在从 \(v_i\) 到 \(v_{i+1}\) 的边，则 顶点 \(v_1, v_2, ..., v_n\) 的序列构成长度为 \(n-1\) 的路径。

path compression¶

在实现 合并/查找 算法时，路径压缩是可在 FIND 步骤中执行的局部优化步骤。一旦找到当前对象所在树的根结点，就可以再次追踪到根的路径，使树中的所有对象都直接指向根结点。这会将树的深度从典型的 \(\Theta(\log n)\) 降低到接近常数。

peripheral storage¶

任何不属于计算机核心处理（即 随机存取存储器 ）的存储设备。一个典型的例子是 磁盘驱动器 。

permutation¶

序列 \(\mathbf{S}\) 的一个排列是以某种顺序排列的 \(\mathbf{S}\) 的 元素 。

persistent¶

在计算机内存的语境中，这指的是当电源关闭时不会丢失其存储信息的内存。

physical file¶

构成 磁盘驱动器 上文件的扇区集合。这与 逻辑文件 形成对比。

physical form¶

将数据类型实现为数据结构。与数据类型的 物理形式 形成对比。

Pigeonhole Principle¶

数学中常用的一个引理。一个典型的变体表述为：当 \(n+1\) 个对象存储在 \(n\) 个位置时，至少有一个位置必须存储两个或更多对象。

pivot¶

在 快速排序 中，用于将线性表分割为子列表的值，其中一个子列表包含小于枢轴的值，另一个包含大于枢轴的值。

platter¶

在 磁盘驱动器 中，指构成驱动器存储空间的一系列扁平磁盘之一。通常，每个盘片的每个表面（顶部和底部）都存储数据，且每个表面都有其自己的 磁头 。

point quadtree¶

用于存储点数据的 空间数据结构 。它类似于 PR 四叉树 ，因为它（在二维空间中）将世界划分为四个部分。然而，它使用 对象空间分解 进行划分。也就是说，包含该点的象限会在该点处被划分为四个部分。它类似于 kd 树 ，后者在每个维度上交替划分，而前者则同时在所有维度上进行划分。

point-region quadtree¶

通常被称为 PR 四叉树 的形式名称。

pointee¶

术语 pointee 指任何被 指针 或 引用 指向的对象。

pointer¶

其值为另一个变量 地址 的变量；一个链接。

pointer-based implementation for binary tree nodes¶

实现 二叉树 结点 的一种常见方法。每个结点存储一个数据值（或指向数据值的 引用 ），以及指向左孩子和右孩子的指针。如果其中一个或两个孩子不存在，则存储空指针。

polymorphism¶

一个 面向对象编程范式 术语，意为*一名多形*。它描述了软件动态改变其行为的能力。存在两种基本形式： 运行时多态 和 编译时多态 。

pop¶

用于表示从 栈 中移除一个 元素 的专用术语。

poset¶

偏序集 的另一个名称是叶结点。

position¶

线性表抽象数据类型的定义性质是，线性表元素处于某个位置。许多线性表抽象数据类型支持按位置访问。

postorder traversal¶

在 二叉树 中， 遍历 首先 递归地 访问 左 子结点 ，然后递归访问右孩子，最后访问 根结点 。

potential¶

一个与 摊还分析 相关的概念。势能是能够完成的总工作量或当前可用工作量。

powerset¶

对于 集合 \(\mathbf{S}\) ，幂集是 \(\mathbf{S}\) 的所有可能 子集 的集合。

PR quadtree¶

一种在二维空间中存储点数据的 四叉树 。PR 四叉树的根表示二维空间中的某个正方形区域。如果该空间存储了多个数据点，则将该区域分解为四个相等的子象限，每个子象限由 PR 四叉树的一个子树 递归地 表示。由于 PR 四叉树的许多叶结点不包含任何数据点，实现时通常使用 享元 设计模式 。与 二叉空间分割树 相关。

practicality window¶

算法的实际用户会为该算法提供的问题输入规模 \(n\) 的取值范围。如果两个算法具有不同的增长率，根据定义其中一个比另一个增长得更快，这意味着超过某个 \(n\) 值后，增长较慢的那个总是更快。但如果该 \(n\) 值超出了任何实际用户可能使用的实用限制，那么渐近更快的算法在实际中也就更快。

prefix property¶

给定一组字符串，若该组中没有任何字符串是组内另一字符串的前缀，则称该组具有前缀性质。其意义在于，对于由该组成员构成的长字符串，可以将其唯一地分解为各个组成成员。一个具有前缀性质的字符串集合的例子是一组 哈夫曼编码 。

preorder traversal¶

在 二叉树 中， 遍历 首先 访问 根结点 ，然后 递归地 访问左 子结点 ，再递归访问右孩子。

Prim's algorithm¶

一个 贪心算法 ，用于计算 图 的 最小成本生成树 。它与求解 单源最短路径问题 的 Dijkstra 算法 几乎完全相同，唯一的区别在于更新已知最佳距离时所执行的计算。

primary clustering¶

在 散列 中，某些 冲突解决 方法倾向于在散列表的某些部分产生聚集。经典示例是 线性探测 。当一组键在冲突解决过程中遵循相同的 探测序列 时，往往会发生这种情况。

primary index¶

主键索引 的同义词。

primary key¶

记录 的唯一标识符。

primary key index¶

将每个 主键 值与指向磁盘上实际记录的指针相关联。

primary storage¶

计算机中速度更快但成本更高的内存，在现代计算机中通常指 随机存取存储器 。这与 辅存 形成对比，后者与主存储设备共同构成计算机的 存储层次结构 。

primitive data type¶

在 Java 中，指一组未作为对象实现的 简单类型 中的一种。一个例子是 int 。

primitive element¶

在集合记号中，这是属于该集合基类型的一个成员元素。这与集合的元素是另一个集合的情况相反。

primitive nth root of unity¶

1 的 \(n\) 次根。通常为 复数 。一种直观的理解方式是复平面中单位圆的 \(n\) 分之一。

priority¶

分配给一组 作业 或任务的量，用于指示处理顺序的重要性。例如，在操作系统中，可能有一组准备运行的进程（作业）。操作系统必须根据其优先级选择下一个要执行的任务。

priority queue¶

一种抽象数据类型，其主要操作包括插入记录和删除最大（或在另一种实现中为最小）值的记录。通常使用 堆 数据结构来实现。该名称源于一个常见应用，其中存储的记录代表任务，而排序值基于任务的 优先级 。

probabilistic algorithm¶

一种 随机化算法 形式，可能产生错误结果，或可能无法产生结果。

probabilistic data structure¶

任何使用 概率算法 执行其操作的数据结构。一个很好的例子是 跳跃表 。

probe function¶

在 散列 中， 冲突解决 方法使用的函数用于计算在 散列表 中下一步查找的位置。

probe sequence¶

在 散列 中， 探测函数 在 冲突解决 期间访问的 槽位 序列。

problem¶

一项待执行的任务。最好将其视为一个 函数 或将输入映射到输出的过程。

problem instance¶

问题的参数的一个特定取值选择。换句话说，问题的一组特定输入。给定问题实例在某个 成本模型 下具有规模。

problem lower bound¶

在 算法分析 中，我们可以针对该 问题 的所有 算法 证明的最紧的 下界 。这通常比确定 问题上界 要困难得多。由于算法的下界在不同情况下（例如 最好情况 或 最坏情况 ）可能差异很大，我们通常需要指明所指的具体情况。

problem upper bound¶

在 算法分析 中，指我们已知的求解该 问题 的最好 算法 的 上界 。由于算法的上界在不同情况下（例如 最好情况 或 最坏情况 ）可能差异很大，我们通常需要指明所指的具体情况。

procedural¶

通常指 过程式编程范式 ，与 面向对象编程范式 相对。

procedural programming paradigm¶

过程式编程使用一系列指令（以及过程调用）来定义要执行的一系列计算步骤。这与 面向对象编程范式 形成对比。

production¶

production rule¶

一个 文法 由产生式规则组成。产生式规则包括 终结符 和 非终结符 ，其中一个非终结符是 开始符号 。每条产生式规则将一个或多个非终结符（可能带有相关的终结符）替换为一个或多个终结符和非终结符。根据对规则形式的限制，存在可以由特定类型文法表示的语言类。一个 推导 是一系列产生式，其结果是一个字符串（即全部为终结符），并且该推导可以表示为一个 分析树 。

program¶

算法在某种编程语言中的一个实例或具体表示。

promotion¶

在某些 平衡树 结构（如 2-3 树 ）中，当一次插入导致结点 溢出 时，就会发生提升操作。对于 2-3 树而言，包含中间值的那个 键 会被送至父结点存储。

proof¶

任何真理的确立，一种证明。

proof by contradiction¶

一种数学证明技术，通过先假设定理为假，然后利用一系列推理得出逻辑矛盾来证明定理。由于当定理为假时会产生逻辑矛盾，因此结论是该定理必须为真。

proof by induction¶

一种类似于 递归 的数学证明技术。它用于证明参数化定理 $S(n)$，即涉及 归纳变量 的定理（例如从 1 到 $n$ 的数字之和）。首先证明该定理对 基本情况 成立，然后证明蕴含关系：只要 $S(n)$ 为真，则 $S(n+1)$ 也为真。另一种变体是 强归纳 。

proving the contrapositive¶

我们可以通过证明 \((\mathrm{not}\ Q) \Rightarrow (\mathrm{not}\ P)\) 来证明 \(P \Rightarrow Q\) 。

pseudo polynomial¶

在复杂度分析中，指算法对 NP 完全 问题所需的时间，该问题在实际应用中仍能可接受地快速运行。一个例子是用于 背包问题 的标准 动态规划 算法。

pseudo random¶

在随机数理论中，这意味着给定序列中的所有过去项，无法在多项式时间内准确预测序列的任何未来项。

pseudo-random probing¶

在 散列 中，这是一个 冲突解决 方法，它存储了从 1 到 散列表 大小的值的随机排列。 探测序列 的项 \(i\) simply 是排列中位置 \(i\) 的值。

push¶

用于表示将 元素 插入到 栈 上的专用术语。

pushdown automata¶

PDA¶

一种 有限状态自动机 ，它在基本 确定有限自动机 机的基础上增加了栈内存。这将可识别的语言集扩展到了 上下文无关语言 。

quadratic binary search¶

QBS¶

有序线性表上 字典查找 或 插值查找 的一种变体。QBS 首先会根据待查找的键值计算在线性表中要检查的位置。如果该位置的值不正确，则算法将沿正确方向以某种步长跳跃，直到确定记录所在的范围边界。然后，它通过重新计算位置并进行更小的跳跃来重复此过程。

quadratic growth rate¶

形如 \(cn^2\) 的增长率函数，其中 \(n\) 是输入规模， \(c\) 是一个常数。

quadratic probing¶

在 散列 中，这是一种 冲突解决 方法，它使用某个二次方程 \(ai^2 _ bi + c\) （针对合适的常数 \(a, b, c\) ）来计算 探测序列 的第 \(i\) 项。最简单的形式是直接使用 \(i^2\) 作为探测序列的第 \(i\) 项。

quadtree¶

一种 满树 ，其中每个内部结点有四个子结点。最通常用于存储二维 空间数据 。与 二叉空间分割树 相关。区别在于四叉树同时分割所有维度，而二叉树在每一层只分割一个维度。因此，将四叉树概念扩展到更多维度需要分裂数量迅速增加（例如，三维空间中为 8）。

queue¶

一种类似线性表的结构，元素仅在一端插入，且仅从另一端移除。

Quicksort¶

一种在 最好情况 和 平均情况 情况下为 \(\Theta(n \log n)\) ，但在 最坏情况 情况下为 \(\Theta(n^2)\) 的排序。然而，合理的实现会使最坏情况仅在极罕见的条件下发生。由于其内部循环紧凑，它在一般情况下往往比任何其他已知排序运行得更好。因此，它是一种在代码库中广泛使用的流行排序。它通过分治法工作：选择一个 枢轴 值，将列表划分为小于或大于该枢轴的两部分，然后对这两部分进行排序。

radix¶

基数 的同义词。数字表示中的位数。例如，我们通常以 10 为基（或基数）来表示数字。十六进制是以 16 为基（或基数）。

radix sort¶

一种排序算法，它通过 \(k\) 位键的记录进行 \(k\) 趟处理来工作，其中每一趟根据当前数位对记录进行排序。在过程结束时，记录将被排好序。如果数位数量相对于记录数量较小，这可能很高效。然而，如果 \(n\) 条记录都具有唯一的键值，则至少需要 \(\Omega(\log n)\) 个数位，从而导致一种 \(\Omega(n \log n)\) 排序算法，其速度往往远慢于其他排序算法，如 快速排序 或 归并排序 。

RAM¶

随机存取存储器 的缩写。

random access¶

在 文件处理 术语中， 磁盘访问 到文件内的一个随机位置。更一般地说，访问文件中任意记录的能力。

random access memory¶

简称 随机存取存储器 ，这是现代计算机中 主存 的典型示例。数据访问时间通常以十亿分之一秒（微秒）为单位衡量，比从磁盘驱动器访问数据快约一百万倍。由于访问时间远快于 辅存 ，RAM 用于保存待立即处理的数据。RAM 是计算机 存储层次结构 的典型组成部分。

random permutation¶

从 \(n!\) 种可能的排列中为包含 \(n\) 个元素的集合选择一种排列，使得每种排列被选中的概率相等。

randomized algorithm¶

涉及某种形式随机性以控制其行为的算法。随机化算法的最终目标是提高性能，超越解决同一问题的确定性算法。这一主题有多种变体。“拉斯维加斯算法”返回正确结果，但所需时间可能优于也可能不优于 确定性算法 。“蒙特卡洛算法”是 概率算法 的一种形式，不保证返回正确结果，但能相对快速地返回结果。

range¶

函数的可能输出集合。

range query¶

返回所有相键值落在指定范围内的记录。

read/write head¶

磁头 的同义词。

rebalancing operation¶

在平衡查找树上执行的操作，例如 AVL树 或 伸展树 ，目的是保持树的 高度平衡 。

recognize¶

在形式语言的研究中，能够可靠地判定某个字符串是否属于给定语言的能力。

record¶

信息集合，通常实现为 面向对象编程语言 中的 对象 。许多数据结构是用于组织记录集合的容器。

recurrence relation¶

递推关系 （或不太正式地称为递归）通过包含一个或多个（较小）自身实例的表达式来定义函数。一个经典例子是阶乘函数 \(F(n) = n*F(n-1)\) 的 递归的 定义。

recurrence with full history¶

递推关系 的一种特殊形式，包含一个求和式，其中含有该递推式的副本。表示 快速排序 平均情况代价的递推式就是一个例子。通常可以使用简单技巧消除这个内部求和式，从而简化递推式的求解。

recursion¶

使用递归调用的过程。如果一个算法调用自身来完成其部分工作，则该算法是递归的。参见 递归 。

recursive call¶

在 递归函数 中，它是函数对自身的调用。

recursive data structure¶

一种由同一数据结构的更小或更简单实例部分组成的数据结构。例如， 链表 和 二叉树 可以被视为递归数据结构。

recursive function¶

包含 递归调用 的函数。

recursively enumerable¶

如果存在一个 图灵机 \(M\) 使得 \(L = L(M)\) ，则语言 \(L\) 是递归可枚举的。

Red-Black Tree¶

二叉搜索树 的一种平衡变体。

reduction¶

在 算法分析 中，指借助另一个问题的渐近界推导出某个 问题 的 渐近界 的过程。具体来说，如果问题 A 可用于解决问题 B，且问题 A 被证明属于 \(O(f(n))\) ，则问题 B 也必然属于 \(O(f(n))\) 。归约常用于表明某些问题的代价至少与排序相当，或表明某些问题是 NP 完全 。

reference¶

一个使程序能够直接访问某个特定 数据项 的值。例如，它可以是文件中存储记录的字节位置，也可以是内存中指向记录的指针。（注意，Java 区分了引用和指针的概念，因为它并不将引用定义为必须是内存中的字节位置。）

reference count algorithm¶

一种用于 垃圾回收 的算法。每当从变量引用某个内存位置时，与该内存位置关联的计数器就会递增。每当该引用被更改或删除时，引用计数就会递减。如果该计数变为零，则该内存被视为可重用空闲内存。如果引用链中存在环，则此方法可能会失败。

reference parameter¶

一个已被 引用传递 的 参数 。此类参数可在函数或方法内部被修改。

reflexive¶

在集合记号中，集合 \(S\) 上的二元关系 \(R\) 是自反的，如果对于所有 \(a \in \mathbf{S}\) 都有 \(aRa\) 。

Region Quadtree¶

一种用于存储二维像素数据的 空间数据结构 。其思想是，树的根结点表示整幅图像，如果与当前结点关联的所有像素不具有相同的值，则将其递归地划分为四个相等的子象限。这在结构上等价于一棵 PR 四叉树 ，仅分解规则有所不同。

regular expression¶

一种使用并、连接和星闭包运算符来指定定义语言的字符串集合的方法。正则表达式定义了某个 正则语言 。

regular grammar¶

且文法为右线性或左线性。每个正则文法都描述一种正则语言。

regular language¶

语言 \(L\) 是正则语言，当且仅当存在一个 确定有限自动机 \(M\) 使得 \(L = L(M)\) 。

relation¶

在集合记号中，集合 \(\mathbf{S}\) 上的关系 \(R\) 是来自 \(\mathbf{S}\) 的 元组 的集合。

replacement selection¶

堆排序 的一种变体，最常用作 外部排序 的一个阶段。给定存储在 数组 中的一组记录，以及一个太大而无法放入 工作内存 的额外记录流，替换选择将通过向输出流发送记录来卸载 堆 ，并尽可能优先从输入流将新记录引入堆，而不是缩小堆的大小。

reserved block¶

在 内存管理器 中，这指的是 内存池 中已分配用于存储从 客户端 接收的数据的空间。这与 空闲块 形成对比，后者代表内存池中未分配给客户端数据存储的空间。

resource constraints¶

资源约束的示例包括用于存储数据的总空间（可能分为主存和磁盘空间约束）以及执行每个子任务所允许的时间。

root¶

在 树 中，树的最顶端 结点 是根结点。树中的所有其他结点都是根的 后代 。

rotation¶

在 AVL树 和 伸展树 中，旋转是对一个结点、其子结点及其孙结点执行的局部操作，可能导致它们之间关系的重新排序。执行旋转的目的是使树更加 平衡的 。

rotational delay¶

当处理一个 磁盘访问 时，所需数据的首字节移动到 磁头 下方所花费的时间。平均而言，这需要磁盘旋转半圈，因此构成了磁盘访问时间的重要部分。

rotational latency¶

旋转延迟 的同义词。

run¶

一系列已排序的记录。这通常指通过 外部排序 进行排序的（已排序）记录子集。

run file¶

在 外部排序 操作期间创建的临时文件，该游程文件包含一组 游程 。外部排序的一种常见结构是首先创建一系列游程（存储在游程文件中），然后将这些游程合并在一起。

run-time polymorphism¶

一种称为重写的 多态 形式。被重写的方法是指实现了一个新方法，其签名与从其 基类 继承的方法相同。请与 编译时多态 比较。

runtime environment¶

程序（特定编程语言）执行的环境。运行时环境负责管理 运行时栈 、 自由存储区 和 垃圾回收器 等活动，并执行程序。

runtime stack¶

程序运行时调用子例程时存储 活动记录 的位置。

scanner¶

编译器 中负责执行 词法分析 的部分。

scope¶

程序中能够查看和访问变量的部分。

search key¶

记录中用于在查找时代表该记录的字段或部分。例如，在客户记录数据库中，我们可能希望按姓名进行查找。此时，姓名字段即用作查找键。

search lower bound¶

在 数组 中查找的问题，其特定变体具有可证明的下界。对于无序数组，其 最坏情况 为 \(\Omega(n)\) 比较 ，通常使用 对抗论证 进行证明。对于有序数组，其最坏情况为 \(\Omega(\log n)\) ，通常使用类似于 排序下界 证明的论证方法进行证明。然而，在平均情况下，可以在 \(O(\log \log n)\) 时间内搜索有序数组。

search problem¶

给定一个特定的键值 \(K\) ，查找问题是在某个记录集合 L 中定位一条 记录 \((k_j, I_j)\) ，使得 \(k_j = K\) （如果存在的话）。 查找 是一种系统的方法，用于定位具有键值 \(k_j = K\) 的记录（或多条记录）。

search tree¶

一种 树 数据结构，使按 键 值查找更高效。作为一种 容器 ，通常使用查找树来实现 索引 。良好的查找树实现将保证插入、删除和查找操作均为 \(\Theta(\log n)\) 。

search trie¶

任何是 字典树 的 查找树 。

searching¶

给定一个 查找键 \(K\) 和某些记录集合 L，查找是一种系统方法，用于在 L 中定位键值为 \(k_j = K\) 的记录（或多个记录）。

secondary clustering¶

在 散列 中，某些 冲突解决 方法倾向于在散列表的某些部分产生聚集。在 一次聚集 中，这是由一组键引起的，这些键不一定散列到同一个槽位，但在冲突解决过程中遵循了相同 探测序列 的很大一部分。二次聚集是由于键散列到表的同一个槽位而产生的（因此，不受键值影响的冲突解决方法必须为所有此类键使用相同的序列）。这个问题可以通过 双重散列 来解决，因为其序列部分由第二个散列函数确定。

secondary index¶

次键索引 的同义词。

secondary key¶

记录中的键字段，例如工资，其中某个特定的键值可能会在多条记录中重复。与记录的 主键 相比，用户更可能将次键用作查找键。

secondary key index¶

将 次键 值与具有该次键值的每条记录的 主键 关联起来。

secondary storage¶

指速度较慢但成本较低的数据存储方式。典型示例包括 磁盘驱动器 、USB 闪存盘或固态硬盘。

sector¶

磁盘驱动器 上的一个空间单位，指磁盘驱动器硬件一次读取或写入的数据量。该值通常为 512 字节。

sector header¶

在磁盘驱动器上，位于 扇区 起始处的一段信息，用于使 磁头 能够识别当前扇区的标识（或等价地，其地址）。

seed¶

在随机数理论中，随机数序列的起始值。通常与任何 线性同余法 一起使用。

seek¶

在 磁盘驱动器 上，将 磁头 从一个 磁道 移动到另一个的操作。这通常被认为是 磁盘访问 期间最昂贵的步骤。

selection sort¶

虽然这种排序在 最好情况 、 平均情况 和 最坏情况 情况下需要 \(\Theta(n^2)\) 时间，但它仅需 \(\Theta(n)\) 次交换操作。因此，在交换操作代价高昂的应用中，它的表现相对较好。它可以被视为对 冒泡排序 的一种优化，其中每次迭代结束前才执行交换。

self-organizing list¶

一种线性表，在一系列查找操作中会利用某些 启发式 来重新排列其元素，以努力提升查找时间。一般而言，查找是从头开始顺序进行的，但自组织启发式策略会尝试将最可能被查找的记录放置在或靠近线性表的前端。虽然通常不如在已排序线性表上的 二分查找 高效，但自组织线性表并不要求线性表保持有序（因此无需承担执行排序操作的开销）。

self-organizing list heuristic¶

一个 启发式 ，用于维护 自组织线性表 。常用的启发式方法包括 移至前端 和 转置 。

separate chaining¶

在 散列 中，是 开散列系统 的同义词

sequence¶

在集合记号中，序列是一个有序的元素集合，其中可能包含重复值的元素。序列有时也称为 元组 或 向量 。

sequential access¶

在 文件处理 术语中，要求文件中的所有记录按顺序访问。或者，指只能顺序访问数据的存储设备，例如磁带驱动器。

sequential fit¶

在 内存管理器 中，搜索 内存池 以寻找足够大的 空闲块 来服务 内存请求 的过程，可能会将剩余空间保留为空闲块。示例包括 首次适配 、 循环首次适配 、 最佳适配 和 最差适配 。

sequential search¶

最简单的查找算法：在 数组 中，只需按照数组元素出现的顺序依次查看。

sequential tree representation¶

一种存储一系列结点值的表示法，仅需最少信息即可重构树结构。这是一种 序列化 树的技术。

serialization¶

将内存中的数据结构表示为字节序列的过程。有时这样做是为了通过网络传输该数据结构，或将其存储在 流 中（例如磁盘上）。 反序列化 从序列化表示中重建原始数据结构。

set¶

一组可区分的 成员 或 元素 。

set former¶

一种通过文本描述来定义集合成员资格的方法。示例： \(\{x\ |\ x\ \mbox{is a positive integer}\}\) 。

set product¶

记作 \(\mathbf{Q} \times \mathbf{P}\) ，笛卡尔积是一个有序对的集合，其中只要 \(a \in \mathbf{P}\) 且 \(b \in \mathbf{Q}\) ，有序对 \((a, b)\) 就属于该积。例如，当 \(\mathbf{P} = \{2, 3, 5\}\) 且 \(\mathbf{Q} = \{5, 10\}\) 时， \(\mathbf{Q} \times \mathbf{P} = \{(2, 5),\ (2, 10),\ (3, 5),\ (3, 10),\ (5, 5),\ (5, 10)\}\) 。

shallow copy¶

复制 引用 或 指针 值而不复制实际内容。

Shellsort¶

一种排序算法，它利用 插入排序 的最好情况代价来改进 \(\Theta(n^2)\) 的 最坏情况 代价。

shifting method¶

一种为 求和 或 递推关系 寻找 闭式解 的技术。

shortest path¶

给定一个 图 ，其 边 上带有距离或 权值 ，两个结点之间的最短路径是总距离或权重最小的路径。最短路径问题的示例包括 单源最短路径问题 和 全点对最短路径问题 。

sibling¶

在 树 中， 结点 \(A\) 的兄弟结点是任何其他与 \(A\) 具有相同 父结点 的结点。

signature¶

在编程语言中，函数的签名由其返回类型及其参数列表和各参数的类型组成。

signature file¶

在文档处理中，签名文件是一种 位图 ，用于指示集合中的哪些文档包含给定键，使得每个键都有一个 位图 。

simple cycle¶

在 图 术语中，如果其对应的 路径 是简单的，则一个 环 是简单的，只不过该环的第一个和最后一个 顶点 是相同的。

simple path¶

在 图 术语中，如果路径上的所有顶点均互不相同，则称 路径 为简单路径。

simple type¶

一个 数据类型 ，其值不包含任何子部分。例如整数。

simulating recursion¶

如果某种编程语言不支持 递归 ，或者你希望更高效地实现递归的效果，可以使用 栈 来维护在递归过程中等待完成的子问题集合。使用循环时，每当原本会进行递归调用，只需将必要的程序状态压入栈中；每当原本会从递归调用返回，就从栈中弹出之前的程序状态。

single rotation¶

一种由 伸展树 和 AVL树 使用的 重平衡操作 类型。

single-source shortest paths problem¶

给定一个 图 ，其 权值 或 边 上带有距离，并指定一个起始 顶点 \(s\) ，求从 \(s\) 到图中其他每个顶点的最短路径。解决此问题的一种算法是 Dijkstra 算法 。

singly linked list¶

一种 链表 实现变体，其中每个链表结点仅包含指向链表中下一个元素的访问指针。

skip list¶

一种 链表 形式，通过添加额外链接来降低插入、删除和查找等基本操作的成本。它是一种 概率数据结构 ，因为它使用 概率算法 添加了额外链接。它比 二叉搜索树 更高效地实现 字典 ，且实现难度大致相当。

slot¶

在 散列 中， 散列表 中的一个位置。

snowplow argument¶

用于直观解释为何 替换选择 会生成平均大小为工作内存两倍的 游程 的一个类比。来自输入流的记录具有键值，其大小可能任意，且与下落雪花的位置相关。替换选择过程类似于在圆形轨道上移动并收集积雪的扫雪机。在稳定状态下，给定相当于 工作内存 大小 \(M\) 的一定量的雪，预计在扫雪机一个周期（类比于替换选择算法的一趟运行）期间，扫雪机前方会落下一定量的雪（即来自输入流的传入记录）。因此，预计扫雪机在一趟（即替换选择的一趟运行）中将收集 \(2M\) 的雪。

software engineering¶

软件工程是对软件的设计、开发和维护进行工程学的研究与应用。

software reuse¶

在 软件工程 中，复用软件组件的概念。具体而言，在创建新软件时使用现有的软件组件（如函数或库）。

solution space¶

问题的可能解。这通常指一个 优化问题 ，其中某些解比其他解更理想。

solution tree¶

在 解空间 中以树的形式对解集施加的次序，通常源自某种算法访问这些解的顺序。

sorted list¶

一个 线性表 ，其中存储在表中的记录按其 键 值升序排列。如果该表使用 基于数组的线性表 实现，则可以使用 二分查找 ，代价为 \(\Theta(\log n)\) 。但插入和删除操作都将需要 \(\Theta(n)\) 时间。

sorting lower bound¶

排序（排序问题）这一 问题 的下界为 \(\Omega(n \log n)\) 。传统上，这通过使用排序算法的 决策树 模型来证明，并认识到任何排序算法的决策树的最小深度为 \(\Omega(n \log n)\) ，因为在排序过程中需要区分 \(n\) 个输入记录的 \(n!\) 种排列。

sorting problem¶

给定一组记录 \(r_1\) 、 \(r_2\) 、...、 \(r_n\) ，其具有 键 个值 \(k_1\) 、 \(k_2\) 、...、 \(k_n\) ，排序问题是将这些记录排列成任意顺序 \(s\) ，使得记录 \(r_{s_1}\) 、 \(r_{s_2}\) 、...、 \(r_{s_n}\) 的键满足性质 \(k_{s_1} \leq k_{s_2} \leq ... \leq k_{s_n}\) 。换句话说，排序问题是将一组记录排列起来，使其键字段的值呈非递减顺序。

space/time tradeoff¶

许多程序可以设计为以额外存储空间为代价来加快处理速度，或以额外处理时间为代价来减少存储空间。

sparse graph¶

一个 图 ，其中实际 边 的数量远小于可能的边数。通常，这意味着图中任何 顶点 的 度 相对较低。

sparse matrix¶

一个值大多为零的矩阵。人们已经开发了多种数据结构来存储稀疏矩阵，其目标是与简单地使用为每个矩阵位置存储值的常规矩阵表示相比，减少表示它所需的空间量。其中一个例子是 正交链表 。

spatial¶

指空间中的位置。

spatial application¶

具有空间方面的应用。特别是，存储需要按位置搜索的记录的应用。

spatial attribute¶

记录的一个属性，它在空间中具有位置，例如坐标。这通常是在二维或更多维中。

spatial data¶

任何具有位置（在空间中）的对象或记录。

spatial data structure¶

一种 数据结构 ，旨在当 空间属性 用作键时支持高效处理。特别是，一种支持按位置高效查找，或在二维及更高维度中查找给定区域内所有记录的数据结构。用于存储点数据的空间数据结构的示例包括 二叉空间分割树 、 PR 四叉树 和 kd 树 。

spindle¶

指 磁盘驱动器 上使 盘片 固定到位的中心转轴。

Splay Tree¶

二叉搜索树 的一种变体实现，其与标准 BST 的不同之处在于使用了修改后的插入和删除方法以保持树的 平衡的 。类似于 AVL树 ，它在插入和删除操作中使用了 旋转 的概念。虽然 Splay Tree 不保证树是平衡的，但它保证对树进行一系列 \(n\) 操作的总代价为 \(\Theta(n \log n)\) ，这意味着任何给定操作都可以视为具有 \(\Theta(\log n)\) 的 摊还成本 。

splaying¶

对 伸展树 执行 重平衡操作 的操作。

stable¶

如果一个排序算法不会改变具有相同 键 值的记录的相对顺序，则称该算法是稳定的。

stack¶

一种类似线性表的结构，元素仅能在一端插入或移除。

stack frame¶

压入调用栈并从中弹出的数据帧

stack variable¶

局部变量 的另一个名称是叶结点。

stale pointer¶

在 缓冲池 或 内存管理器 的上下文中，这意味着指向一个 引用 或不再有效的内存位置的 缓冲区 。例如，程序可能会向缓冲区池发出内存请求，并获得对保存所请求数据的缓冲区的引用。随着时间的推移，由于不活动，该缓冲区的内容可能会被刷新。如果持有该缓冲区引用的程序随后尝试再次访问该缓冲区的内容，则数据内容将已发生变化。这种情况发生的可能性取决于缓冲区池系统接口的设计。某些设计使这种情况不可能发生。其他设计则允许这种情况发生，以试图提供更高的性能。

start state¶

在 有限自动机 中，机器开始计算时始终处于的指定状态。

start symbol¶

在 文法 中，指定的 非终结符 是语言中字符串 推导 的起始点。

state¶

某事物在某一时刻所处的条件。在计算中，这通常指某一时刻任何现有变量的集体值。在 自动机 中，状态是一种抽象条件，可能带有相关信息，其主要定义为自动机可从当前状态转换到另一状态的条件。此类状态通常由表示自动机的图中的结点来表示。

State Machine¶

有限自动机 的同义词。

static¶

不发生改变的事物（与 动态的 相对）。在计算机编程中，静态通常指在编译时发生的事情。例如，静态分析是对程序的文本或结构进行分析，而不是对其运行时行为进行分析。静态绑定或静态内存分配发生在编译时。

static scoping¶

词法作用域 的同义词。

Strassen's algorithm¶

矩阵乘法的 递归的 算法。当相乘两个 \(n \times n\) 矩阵时，该算法的运行速度快于标准矩阵乘法算法所需的 \(\Theta(n^3)\) 时间。具体而言，Strassen 算法需要 \(Theta(n^{\log_2 7})\) 时间。这是通过重构子矩阵乘法和加法操作实现的，从而仅需 7 次子矩阵乘法而非 8 次，代价是增加了额外的子矩阵加法操作。因此，尽管渐近成本更低，但增长率方程中的常数因子更高。这使得 Strassen 算法在实际应用中效率低下，除非被相乘的数组相当大。存在 Strassen 算法的变体，它们以更多子矩阵加法为代价，进一步减少了子矩阵乘法的次数。

strategy¶

一种完成任务的方法，通常被封装为算法。也是 设计模式 的名称，它将执行任务的算法与控制该任务应用于集合中每个成员的过程分离开来。一个很好的例子是通用排序函数，它接收一组记录（例如 数组 ）以及一种“策略”，该策略以算法形式存在，能够知道如何从数组中的记录提取键。它与 访问者 设计模式仅有细微差别，主要区别在于意图而非语法。策略设计模式专注于封装作为更大过程一部分的活动，以便可以替换执行该活动的不同方式。访问者设计模式则专注于封装将对集合中所有成员执行的活动，以便在访问所有集合成员的通用方法中可以替换完全不同的活动。

stream¶

以 序列化的 形式交付内容的过程。

strict partial order¶

在集合记号中，一个关系是 非自反 、 反对称 和 传递 。

strong induction¶

归纳证明 中 归纳步骤 的另一种表述形式。强归纳法的归纳步骤为：若 Thrm 对所有 \(k, c \leq k < n\) 成立，则 Thrm 对 \(n\) 成立。

subclass¶

在 面向对象编程范式 中，任何从其他类 继承 的 类层次结构 内的类。

subgraph¶

子图 \(\mathbf{S}\) 由从 图 \(\mathbf{G}\) 中选择 \(\mathbf{G}\) 的 顶点 的一个 子集 \(\mathbf{V}_s\) 以及 \(\mathbf{G}\) 的 边 的一个子集 \(\mathbf{E}_s\) 形成，使得对于每条边 \(e \in \mathbf{E}_s\) ， \(e\) 的两个顶点都在 \(\mathbf{V}_s\) 中。

subset¶

在集合论中，集合 \(A\) 是集合 \(B\) 的子集，或者等价地说 \(B\) 是 \(A\) 的 超集 ，如果 \(A\) 的所有元素也都是 \(B\) 的元素。

subtract-and-guess¶

一种为 求和 或 递推关系 寻找 闭式解 的技术。

subtree¶

子树是二叉树结点的 子集 ，它包含树中的某个结点 \(R\) 作为子树的 根结点 ，以及 \(R\) 的所有 后代 。

successful search¶

当在记录集合中查找 键 值时，我们可能会找到它。如果是这样，我们称其为成功查找。另一种情况是 不成功查找 。

summation¶

对某个 函数 应用于一组参数值时的成本总和。通常使用 Sigma 记号表示。例如，从 1 到 \(n\) 的整数之和可以写作 \(\sum_{i=1}^{n} i\) 。

superset¶

在集合论中，若 \(A\) 的所有 元素 也是 \(B\) 的元素，则集合 \(A\) 是 集合 \(B\) 的 子集 ，或等价地， \(B\) 是 \(A\) 的 超集 。

symbol table¶

作为 编译器 的一部分，符号表存储程序中的所有标识符，以及编译器执行任务所需的关于该标识符的任何必要信息。

symmetric¶

在集合记号中，关系 \(R\) 是对称的，如果对于所有 \(a, b \in \mathbf{S}\) ，只要 \(aRb\) ，那么 \(bRa\) 。

symmetric matrix¶

一个等于其 转置 的方阵。等价地，对于一个 \(n \times n\) 矩阵 \(A\) ，对所有 \(i,j < n\) ，有 \(A[i, j] = A[j, i]\) 。

syntax analysis¶

编译 的一个阶段，接受 记号 ，检查程序语法是否正确，然后生成 分析树 。

tail¶

一个 线性表 的末尾。

terminal¶

出现在 产生式规则 中的特定字符或字符串。与 非终结符 不同，后者表示产生式中的一个抽象状态。类似于 字面量 ，但该术语更常用于 编译器 的上下文中。

testing¶

确定程序是否按预期运行。这与 调试 形成对比。

Theta notation¶

在 算法分析 中， \(\Theta\) 记号用于表示 算法 或 问题 的 上界 和 下界 相匹配。

token¶

程序的基本逻辑单元，由 词法分析 确定。这些包括算术运算符、语言关键字、变量或函数名，以及数字。

tombstone¶

在 散列 中，墓碑用于标记 散列表 中已删除记录的 槽位 。其目的是允许 冲突解决 过程探测该槽位（从而避免删除记录后 探测序列 中更靠下的记录变得不可达），同时允许该槽位被未来的插入操作重用。

topological sort¶

将 有向无环图 的 顶点 排列成 线性序 的过程，使得顺序中没有任何顶点 \(A\) 的前面存在能从 \(A\) 通过（有向） 路径 到达的顶点。通常，图中的（有向）边定义了一个先决条件系统，而拓扑排序的目标是以一种不违反任何先决条件的顺序列出顶点。

total order¶

集合上的二元关系，其中集合中每一对不同元素都是 可比较的 （即可以确定哪一对元素更大）。

total path length¶

在 树 中，每个 结点 的 层 之和。

Towers of Hanoi problem¶

递归算法的一个标准示例。该问题始于左柱上按递减顺序堆叠的一摞圆盘（每个圆盘大小唯一），以及另外两根柱子。问题的目标是将这些圆盘移动到右柱，约束条件是每次只能移动一个圆盘，且圆盘绝不能放在比它小的圆盘之上。对于 \(n\) 个圆盘，此问题需要 \(\Theta(2^n)\) 次移动。标准解法是先将 \(n-1\) 个圆盘移到中间柱，再将最底部的圆盘移到右柱，最后将中间柱上的 \(n-1\) 个圆盘移到右柱。

track¶

在 磁盘驱动器 上，一个同心圆代表了 磁头 在磁盘旋转时能够读取的所有 扇区 。其意义在于，对于 I/O 磁头的给定位置，可以读取磁道上的扇区而无需执行（相对昂贵的） 寻道 操作。

track-to-track seek time¶

从随机 磁道 到相邻磁道执行 寻道 操作的期望（平均）时间。因此，这可以视为 磁盘驱动器 的最小可能寻道时间。这是磁盘驱动器供应商通常提供的两个磁盘性能指标之一，另一个是 平均寻道时间 。

trailer node¶

在 链表 或相关结构的实现中常用，此 结点 位于线性表的最后一个元素之后。其目的是通过减少必须编程处理的特殊情况数量来简化代码实现。

transducer¶

一种接收输入并产生输出的机器。 图灵机 是换能器的一个例子。

transitive¶

在集合记号中，关系 \(R\) 是传递的，如果对于所有 \(a, b, c \in \mathbf{S}\) ，只要 \(aRb\) 且 \(bRc\) ，则 \(aRc\) 。

transpose¶

在线性代数的语境中，矩阵 \(A\) 的转置是另一个矩阵 \(A^T\) ，它是通过将 \(A\) 的行写为 \(A^T\) 的列而创建的。在 自组织线性表 的语境中，转置是一种用于维护列表的 启发式 。在此启发式方法下，每当访问一条记录时，它都会向列表前端移动一个位置。

trap state¶

在 有限状态自动机 中，指所有转换都循环回自身的那种状态。这样的状态可能是 终态 。

traversal¶

任何按某种顺序访问集合（如 树 或 图 ）中所有对象的过程。

tree¶

树 \(\mathbf{T}\) 是一个由一个或多个 结点 组成的有限集合，其中有一个指定的结点 \(R\) ，称为 \(\mathbf{T}\) 的 根结点 。如果集合 \((\mathbf{T} -\{R\})\) 非空，则这些结点被划分为 \(n > 0\) 不相交集合 \(\mathbf{T}_0\) 、 \(\mathbf{T}_1\) 、...、 \(\mathbf{T}_{n-1}\) ，它们各自都是树，并且它们的 根结点 \(R_1, R_2, ..., R_n\) 分别是 \(R\) 的 子结点 。

tree traversal¶

在树上执行的 遍历 。传统的树遍历包括适用于 二叉的 和 一般的 树的 前序 与 后序 遍历，以及最适合 二叉搜索树 的 遍历 。

trie¶

一种 查找树 形式，其中内部结点表示在预定位置对 键空间 进行分割，而不是基于实际看到的 键 值进行分割。例如，一个用于键值范围 0 到 1023 的简单二叉查找字典树，会将所有键值小于 512 的记录存储在树的左侧，而将所有键值大于或等于 512 的记录存储在树的右侧。字典树始终是一棵 满树 。据传，该术语源自"retrieval"（检索），应发音为"try"（与"tree"相对，以区分查找树与查找字典树在空间分解方法上的差异）。术语"trie"有时也用作 字母表字典树 的同义词。

truth table¶

在符号逻辑中，一种表格，其行包含布尔变量的所有可能组合，并有一列显示当给定该行对布尔变量的真值赋值时表达式的结果（真或假）。

tuple¶

在集合记号中，是 序列 的另一种说法。

Turing machine¶

一种 有限自动机 类型，虽然可以完全简单地定义，但能够执行任何已知计算机所能执行的计算。

Turing-acceptable¶

如果存在某个 图灵机 能够 接受 一种语言，则该语言为 \(Turing-acceptable\) 。也就是说，若字符串属于该语言，机器将停机于接受状态；若字符串不属于该语言，机器将进入 悬挂配置 。

Turing-computable function¶

任何存在图灵机能够执行必要工作以计算该函数的函数。

Turing-decidable¶

如果存在一台图灵机，能够明确地指出任意字符串是否属于该语言，则该语言是图灵可判定的。每个图灵可判定语言也是图灵可接受的，因为那台能判定字符串是否属于该语言的图灵机可以被修改为：若字符串不属于该语言，则进入 悬挂配置 。

two-coloring¶

将两种颜色分配给图像中的区域，使得任何两个共享边的区域颜色不同。

type¶

一组值。

unary notation¶

一种表示 自然数 的方法，其中零的值由空字符串表示，而值 \(n\) 由一系列 \(n\) 标记表示。

uncountably infinite¶

uncountable¶

如果一个集合无法映射到整数集，则该无限集是不可数无限的。这通常使用 对角化论证 来证明。实数集就是一个不可数无限集的例子。

underflow¶

实体中存储的数据量低于某个最小阈值的情况。例如， B 树 中的结点必须至少半满。如果删除记录导致结点不满一半，则处于下溢状态，必须采取措施纠正此情况。

undirected edge¶

连接两个 顶点 且无方向的 边 。许多图表示会用两个 有向边 来表示这样的边。

undirected graph¶

一个 图 ，其 边 没有方向。

uninitialized¶

未初始化的变量表示它没有初始值。

UNION¶

管理 不相交集合 的 合并/查找 算法的一半。它是通过使其中一棵树的根结点将其父指针指向另一棵树的根结点，来合并两棵使用 父指针表示 表示的树的过程。

UNION/FIND¶

维护不相交集合族的过程。 查找 操作确定给定对象属于哪个不相交集合，而 合并 操作在判定两个不相交集合在某 等价关系 下属于同一 等价类 的成员时，将这两个集合合并。

unit production¶

单位产生式是 文法 中形如 \(A \rightarrow B\) 的 产生式 ，其中 \(A, B \in\) 该文法的 非终结符 集合。任何包含单位产生式的文法都可以被重写以消除它们。

unsolveable problem¶

一个被证明无法在计算机上解决的问题。经典例子是 停机问题 。

unsorted list¶

一种 线性表 ，其中存储在表中的记录可以以任意顺序出现（与 有序表 相反）。无序表可以支持高效的（ \(\Theta(1)\) ）插入时间（因为您可以将记录放在任何方便的位置），但查找和删除都需要 \(\Theta(n)\) 时间。

unsuccessful search¶

当在记录集合中查找 键 值时，我们可能找不到它。如果是这样，我们称其为不成功查找。通常我们要求这意味着集合中没有任何记录实际上具有该键值（尽管 概率算法 的查找可能不要求这一点）。与不成功查找相对的是 成功查找 。

unvisited¶

在 图 算法中，这指的是在算法当前阶段尚未被处理的结点。此信息通常通过一个 标记数组 来维护。

upper bound¶

在 算法分析 中， 增长率 始终大于或等于所讨论 算法 的增长率。在实践中，这是我们所知的增长最慢的函数，它至少与除常数个输入外的所有输入一样快。它可能是对真实情况的高估。由于算法的上界在不同情况下（例如 最好情况 或 最坏情况 ）可能差异很大，我们通常需要指明所指的具体情况。

value parameter¶

一个已被 值传递 的 参数 。在函数或方法内部修改此类参数不会影响调用参数的值。

variable-length coding¶

给定一组对象，变长编码方案为集合中的每个对象分配一个码字，这些码字的长度可以不同。通常，这种做法会使得最可能使用的对象拥有最短的码字，其目标是最小化表示对象序列所需的总空间，例如在表示文档中的字符时。 哈夫曼编码 是变长编码方案的一个示例。这与 定长编码 形成对比。

vector¶

在集合记号中，是 序列 的另一种说法。作为数据结构，术语“向量”通常用作 动态数组 的同义词。

vertex¶

结点 在 图 中的另一个名称是空指针。

virtual memory¶

一种内存管理技术，使程序能够将相对快速但容量较小的内存视为更大的空间。庞大的“虚拟”数据空间实际上存储在相对缓慢但容量较大的 后备存储 设备上，并通过 缓冲池 按需将部分数据复制到较小、更快的内存中。一个常见的例子是使用 随机存取存储器 来管理对实际存储在 磁盘驱动器 上的大型虚拟空间的访问。程序员可以像所有数据内容都存储在 RAM 中那样实现程序，即使该空间大于可用的物理 RAM，从而更易于实现。

visit¶

在 遍历 对 图 或 树 的过程中，每个 结点 上发生的动作。

visited¶

在 图 算法中，这指的是在算法当前阶段之前已被处理过的结点。此信息通常通过使用 标记数组 来维护。

visitor¶

一个 设计模式 ，其中 遍历 进程被赋予一个函数（称为访问者），该函数应用于被遍历集合中的每个对象。例如，通用的树或图遍历可以设计为接受一个函数参数，该函数应用于每个结点。

volatile¶

在计算机内存的语境中，这指的是当电源关闭时会丢失所有存储信息的内存。

weight¶

与 图 中的 边 最常关联的成本或距离。

weighted graph¶

一个 图 ，其每个 边 都关联有一个 权值 或代价。

weighted path length¶

给定一棵树，并为树中的每个叶结点赋予一个 权值 ，则该叶结点的加权路径长度为其权重乘以其 深度 。

weighted union rule¶

当使用 合并/查找 算法合并两个不相交集合时，加权联合规则用于确定哪个子树的根指向另一个。结点较少的子树的根将被设置为指向结点较多的子树的根。通过这种方式，所得树中结点的平均深度将小于反向赋值的情况。

working memory¶

算法可用的 主存 部分。通常指为处理存储在 外围存储 中的大量数据的算法所提供的主存，工作内存表示可以容纳正在处理的总数据子集的空间。

worst case¶

在算法分析中，最坏情况是指对于给定输入规模 \(n\) 的所有问题实例中成本最高的那个 问题实例 。注意，最坏情况**并非**指当 \(n\) 很大时，因为我们指的是某一类输入中的最坏情况（即，我们想要的是规模为 \(n\) 的那些输入中最差的那个）。

worst fit¶

在 内存管理器 中，最坏适应法是决定从 内存池 分配内存时使用哪个 空闲块 的 启发式 。最坏适应法总是从最大的空闲块进行分配。其理由是，这种方法最不可能导致以小型、不可用内存块形式出现的 外部碎片 。其缺点是，它倾向于消除异常大请求所需的大型空闲块的可用性。

zigzig¶

重平衡操作 使用的一种 伸展树 类型。

Zipf distribution¶

一种遵循齐夫定律的数据分布，该定律是一项经验观察，指出在物理和社会科学中研究的许多类型数据都遵循幂律概率分布。也就是说，当数据集合按频率排序时，任何记录的频率与其排名成反比。因此，出现最频繁的记录其频率远高于次频繁的记录，而次频繁记录的频率又远高于第三频繁的记录（但其比率略低于前两条记录之间的比率），依此类推。图 80/20 规则 是对齐夫分布的一种通俗描述。遵循齐夫分布对于 缓存 或 自组织线性表 的成功运行至关重要。

zone¶

在 内存管理器 中，这一概念指的是 内存池 的不同部分以不同方式进行处理。例如，部分内存可能由一个简单的 freelist 处理，而内存池的其他部分则由一个 顺序适配 内存管理器处理。在 磁盘驱动器 上，区域的概念与最大数据密度存在限制这一事实相关，同时结合每个磁道的扇区需使用相同角距离这一事实，意味着离磁盘中心越远的磁道其密度会逐渐降低。在这种情况下，区域是一系列相邻的磁道，其数据密度由该区域内最内侧磁道的最大密度决定。下一个区域则可以为其最内侧磁道重新设定数据密度，从而在保持每个扇区角距离的同时获得更大的总存储空间。