2-SAT 判断每个子句至多含两个文字的布尔公式是否存在满足赋值,可在线性时间内求解。
two-sat3SUM问题3SUM问题旨在判断一组数中是否存在三个元素之和为零,是细粒度复杂度理论中的基准问题。
3sum-problem阿姆达尔定律阿姆达尔定律描述了计算中未受改进影响的部分如何限制整体加速比,尤其适用于增加并行处理器的情形。
amdahls-law艾伦·图灵艾伦·图灵是英国数学家和密码破译专家,其研究奠定了计算机科学、人工智能与数学生物学的基础。
alan-turing贝尔曼–福特算法贝尔曼–福特算法求解含负权边的加权图中的单源最短路径,并检测从源点可达的负权环。
bellman-ford-algorithm背包问题背包问题研究如何从重量和价值已知的物品中进行选择,使总重量不超过容量限制,同时使总价值最大。
knapsack-problem泵引理泵引理给出某类形式语言必须满足的重复性质,常用于证明语言不是正则语言或上下文无关语言。
pumping-lemma比特比特是二进制数位,也是信息量的单位,是数字计算、存储与通信的基础。
bit编辑距离编辑距离是通过插入、删除、替换等指定操作将一个序列转换为另一个序列所需的最小总成本。
edit-distance并行计算并行计算同时利用多个处理资源执行计算任务的不同部分,以提高速度或处理更大规模的问题。
parallel-computing博弈树博弈树表示博弈中可能的行动序列及结果,用于分析策略决策和设计计算机博弈算法。
game-tree布尔可满足性问题布尔可满足性问题判定是否存在使布尔公式为真的赋值,连接计算复杂性理论与实用的自动推理。
boolean-satisfiability-problem插入排序插入排序逐个元素构建有序序列,仅需常数辅助空间,适用于小规模或接近有序的输入。
insertion-sort抽象数据类型抽象数据类型通过可观察的行为规定值及其操作,而不依赖具体的表示或实现方式。
abstract-data-type达梅劳–莱文斯坦距离达梅劳–莱文斯坦距离是将一个字符串变为另一个所需的插入、删除、替换及相邻交换操作的最少次数。
damerau-levenshtein-distance大Θ记号大Θ记号描述函数增长的渐近紧确界,忽略常数因子及输入规模较小时的行为。
big-theta-notation大Ω记号大Ω记号表示函数的渐近下界,常用于描述输入规模增长时计算资源需求的下界。
big-omega-notation戴克斯特拉算法戴克斯特拉算法通过反复确定尚未定案的最近顶点,在边权非负的图中计算最短路径。
dijkstra-algorithm倒排索引倒排索引将词项或其他索引特征映射到包含它们的文档,支持高效的全文搜索、筛选和排序检索。
inverted-index低密度奇偶校验码低密度奇偶校验码利用稀疏的奇偶校验约束和迭代译码,保护传输或存储的信息免受错误影响。
low-density-parity-check-code递归递归通过自身的更简单实例来定义结构或计算,是数学定义和许多算法的基础。
recursion递归函数递归函数将有效计算形式化,并通过引用所定义函数自身的规则来规定计算。
recursive-functions迭代迭代是反复执行某一过程,用于遍历数据、改进近似解、解决计算问题,以及逐步开发软件。
iteration动态规划一种通过组合并复用子问题的解来求解具有特定结构的问题的数学与计算方法。
dynamic-programming动态数组动态数组是一种可调整长度的序列,支持常数时间的按索引访问,以及摊还常数时间的尾部插入。
dynamic-array堆排序堆排序是一种原地比较排序算法,利用二叉堆以常数辅助空间实现最坏情况下 O(n log n) 的运行时间。
heapsort队列(数据类型)队列是一种先进先出的抽象数据类型,用于有序处理、缓冲、通信和算法遍历。
queue-data-type多边形三角剖分多边形三角剖分将多边形区域划分为内部互不重叠的三角形,广泛用于几何算法、图形处理和数值模拟。
polygon-triangulation二叉堆二叉堆是满足堆序约束的完全二叉树,可高效访问和移除最小或最大元素。
binary-heap二叉树二叉树是一种有根数据结构,每个节点最多有两个可区分的子节点,可用于搜索、优先队列、表达式处理和层次化计算。
binary-tree二叉搜索树二叉搜索树按层次组织键,支持查找、更新和有序查询,其效率取决于树的高度。
binary-search-tree二分查找二分查找通过反复排除约一半的剩余候选项,在有序搜索空间中定位目标值或边界。
binary-search分布式共识分布式共识使独立的计算进程在发生故障、通信延迟或恶意行为时,仍能就共同决策达成一致。
distributed-consensus分治法一种算法设计范式,通过将问题分解为较小的子问题并合并其解来求解原问题。
divide-and-conquer弗洛伊德–沃舍尔算法弗洛伊德–沃舍尔算法利用动态规划,计算加权图中所有顶点对之间的最短路径距离。
floyd-warshall-algorithm复杂性类复杂性类根据求解所需的资源、计算模型及正确性条件,对计算问题进行分类。
complexity-class格罗弗算法格罗弗算法在无结构搜索空间中查找标记项,所需预言机查询次数相较经典搜索具有平方级加速。
grovers-algorithm广度优先搜索广度优先搜索按距离逐层探索图,并在所有边的代价相等时求出最短路径。
breadth-first-search归并排序一种基于比较的排序算法,将数据划分为较小的序列,再将排好序的序列合并为完整的有序结果。
merge-sort哈夫曼编码哈夫曼编码为给定的符号分布构造变长前缀码,使平均码字长度最小。
huffman-coding哈希表哈希表通过计算数组位置存储键及其关联值,在哈希方式和容量适当时,可实现快速查找、插入和删除。
hash-table哈希函数哈希函数将数据映射为紧凑的值,用于高效查找、比较和分布,并可在具备适当安全性质时提供密码学保护。
hash-function汉明距离汉明距离统计两个等长序列中符号不同的位置数,是纠错码和离散数据比较中的基本度量。
hamming-distance红黑树红黑树是一种自平衡二叉搜索树,通过颜色不变式保证查找、插入和删除操作的时间复杂度为对数级。
red-black-tree混叠混叠指不同信号经采样后无法区分,产生虚假频率或图案;在编程中则指多个引用指向同一存储位置。
aliasing极小极大算法极小极大算法是一种对抗搜索算法,假定对手采取最优策略,据此选择能取得最佳结果的行动。
minimax计算复杂性计算复杂性研究解决计算问题所需的资源,以及高效计算的极限。
computational-complexity计算机科学计算机科学研究计算、算法、信息处理,以及软件和计算机系统的基本原理。
computer-science计算几何计算几何研究表示、分析和处理几何对象的算法与数据结构,应用于空间搜索、图形学、工程和机器人学。
computational-geometry计算模型计算模型以形式化方式规定计算过程如何运行、能计算什么,以及消耗哪些资源。
model-of-computation加性白高斯噪声信道加性白高斯噪声信道通过在发送信号上叠加与信号独立、功率谱平坦的高斯噪声来描述通信过程。
additive-white-gaussian-noise-channel近似算法近似算法能高效求得优化问题的可行解,并以数学证明保证其与最优解的差距。
approximation-algorithm纠错码纠错码为数据加入有结构的冗余,使解码器能在出现一定传输或存储错误时恢复信息。
error-correcting-code局部敏感哈希局部敏感哈希以较高概率将相似对象映射到相同哈希值,从而实现高效的近似相似性搜索。
locality-sensitive-hashing柯尔莫哥洛夫复杂度柯尔莫哥洛夫复杂度以有限对象的最短有效描述的长度,度量该对象所含的信息量。
kolmogorov-complexity可计算性理论可计算性理论研究算法能够解决哪些问题,并对不可解性的数学界限与程度进行分类。
computability-theory可满足性模理论可满足性模理论结合布尔推理与数学理论,判断逻辑约束是否存在模型。
satisfiability-modulo-theories空间复杂度空间复杂度衡量在指定计算模型和计量约定下,算法所需内存随输入规模增长的情况。
space-complexity快速排序快速排序是一种基于划分的排序算法,期望运行时间为 \(O(n\log n)\),且有高效的原地实现。
quicksort快速选择快速选择通过分区在无序集合中寻找指定秩的元素,随机选择枢轴时期望运行时间为线性。
quickselect