算法与数据结构 术语表

A

术语	英文	释义
摊还分析	Amortized Analysis	评估数据结构上一系列操作的平均代价，不依赖概率，保证对任意操作序列成立
聚合分析	Aggregate Method	摊还分析的一种方法，计算n个操作的总代价上界T(n)，则每个操作摊还代价为T(n)/n
ASL	Average Search Length	平均查找长度，衡量查找算法效率的指标，分为查找成功ASL和查找失败ASL
AVL树	AVL Tree	最早的平衡二叉搜索树，任意节点的左右子树高度差不超过1，查找/插入/删除均为O(log n)

B

术语	英文	释义
回溯	Backtracking	系统搜索解空间并在不满足约束时回退的策略，本质是DFS加剪枝，适用于N皇后、子集生成等问题
Bellman-Ford算法	Bellman-Ford Algorithm	单源最短路径算法，支持负权边，对所有边执行V-1轮松弛，时间O(VE)
大O符号	Big-O Notation	渐进上界符号，f(n)=O(g(n))表示f(n)的增长速率不超过g(n)的某个常数倍
大Omega符号	Big-Omega Notation	渐进下界符号，f(n)=Omega(g(n))表示f(n)的增长速率至少为g(n)的某个常数倍
大Theta符号	Big-Theta Notation	渐进紧界符号，f(n)=Theta(g(n))表示f(n)与g(n)同阶增长
二分搜索	Binary Search	在有序数组中每次将搜索范围缩小一半的查找算法，时间O(log n)
分支限界	Branch and Bound	BFS搜索加下界剪枝的策略，适用于TSP、整数规划等优化问题
广度优先搜索	BFS	按层次逐步扩展的图遍历算法，使用队列实现，天然保证无权图最短路径
桶排序	Bucket Sort	将元素分配到有限数量的桶中，桶内单独排序后合并，平均O(n+k)
布隆过滤器	Bloom Filter	用位数组近似表示集合的概率数据结构，查询O(k)，存在假阳性但无假阴性

C

术语	英文	释义
链表	Linked List	通过指针连接的离散内存线性数据结构，插入删除O(1)，随机访问O(n)
循环链表	Circular Linked List	尾节点的next指向头节点的链表，适合循环队列等场景
计数排序	Counting Sort	统计每个值出现次数的非比较排序，时间O(n+k)，适用于整数范围有限的场景
竞争分析	Competitive Analysis	将在线算法代价与最优离线算法代价比较来评估性能，竞争比越接近1越好
连通分量	Connected Component	无向图中的极大连通子图，可通过BFS/DFS求解
割点	Articulation Point	删除该顶点后图不再连通的节点，可用Tarjan算法在O(V+E)时间内求解
桥	Bridge	删除该边后图不再连通的边，判定条件为low[v] > dfn[u]
冒泡排序	Bubble Sort	相邻比较交换的排序算法，平均O(n^2)，稳定，可提前终止优化
鸡尾酒排序	Cocktail Sort	双向冒泡排序，交替从左到右和从右到左遍历

D

术语	英文	释义
深度优先搜索	DFS	沿一条路径尽可能深入再回溯的图遍历算法，使用栈/递归实现，适用于环检测、拓扑排序
Dijkstra算法	Dijkstra’s Algorithm	非负权图单源最短路径算法，贪心策略加松弛操作，二叉堆实现O(E log V)
动态规划	Dynamic Programming	通过记忆化避免重复计算的算法范式，依赖最优子结构和无后效性
动态数组	Dynamic Array	容量满时自动扩容的数组，append操作摊还O(1)
度	Degree	与顶点关联的边数，有向图分为入度和出度
稠密图	Dense Graph	边数接近V^2的图，适合用邻接矩阵表示

E

术语	英文	释义
编辑距离	Edit Distance	将一个字符串转换为另一个字符串所需的最少操作次数，允许插入、删除、替换
边的分类	Edge Classification	DFS中将边分为树边、回边、前向边、横叉边，回边表示存在环

F

术语	英文	释义
斐波那契堆	Fibonacci Heap	通过延迟合并和级联剪切实现高效操作的堆，插入O(1)摊还，删除最小O(log n)摊还
Floyd-Warshall算法	Floyd-Warshall Algorithm	全源最短路径算法，基于DP，时间O(V^3)，支持负权边

G

术语	英文	释义
贪心算法	Greedy Algorithm	每步取局部最优的算法范式，依赖贪心选择性质和最优子结构
图	Graph	由顶点集V和边集E组成的数据结构，分为有向图、无向图、加权图等
邻接矩阵	Adjacency Matrix	用二维数组adj[i][j]表示顶点i到j的边，适合稠密图，空间O(V^2)
邻接表	Adjacency List	每个顶点维护链表存储邻接点，适合稀疏图，空间O(V+E)

H

术语	英文	释义
哈希表	Hash Table	通过哈希函数将键映射到数组下标实现O(1)平均查找的数据结构
哈希函数	Hash Function	将键映射到有限槽位的函数，设计目标是均匀分布、减少冲突
哈希冲突	Hash Collision	不同键映射到同一槽位的现象，处理方法包括链地址法和开放寻址法
负载因子	Load Factor	哈希表中元素数量与槽位数的比值alpha=n/m，通常控制在0.75以下
堆	Heap	满足堆序性质的完全二叉树，最大堆父节点>=子节点，最小堆反之
堆排序	Heap Sort	利用堆数据结构排序，先建堆再反复取堆顶，时间O(n log n)，空间O(1)
霍尔分区	Hoare Partition	快速排序的双指针分区方案，从两端向中间扫描交换逆序对
哈夫曼编码	Huffman Coding	贪心算法构造的最优前缀编码，频率高的字符用短编码

I

术语	英文	释义
插入排序	Insertion Sort	将元素逐个插入已排序部分的排序算法，最好O(n)，稳定，适合小规模或近乎有序数据
内省排序	Introsort	C++ STL的sort实现，先快速排序，递归过深时切换堆排序，小规模切换插入排序
原地排序	In-place Sort	仅需O(1)额外空间的排序算法

K

术语	英文	释义
Kruskal算法	Kruskal’s Algorithm	基于并查集的贪心最小生成树算法，按边权从小到大选取，时间O(E log E)
Kadane算法	Kadane’s Algorithm	求最大子数组和的线性时间算法，维护当前和与最大和

L

术语	英文	释义
线性搜索	Linear Search	逐个比较的朴素查找算法，时间O(n)，适用于无序小规模数据
Lomuto分区	Lomuto Partition	快速排序的分区方案，以最后一个元素为pivot，维护分界指针
最长公共子序列	LCS	两个序列中最长的不要求连续的公共子序列，DP求解时间O(mn)
最长递增子序列	LIS	数组中最长的严格递增子序列，O(n log n)解法使用贪心加二分
LRU缓存	LRU Cache	最近最少使用缓存替换策略，k-竞争，使用哈希表加双向链表实现

M

术语	英文	释义
主定理	Master Theorem	分析分治递推式T(n)=aT(n/b)+f(n)的通用定理，分三种情形
归并排序	Merge Sort	分治排序算法，递归分成两半分别排序后合并，时间O(n log n)，稳定
最小生成树	Minimum Spanning Tree	连通加权无向图中权值之和最小的生成树，Kruskal和Prim为经典算法
记忆化搜索	Memoization	自顶向下的DP实现，用数组/哈希表缓存已计算结果避免重复计算
多重背包	Multiple Knapsack	第i个物品有s[i]个可用的背包问题，二进制拆分优化至O(nW log S)

N

术语	英文	释义
NP类	Nondeterministic Polynomial Time	可在非确定性图灵机上多项式时间求解的判定问题类，等价于多项式时间可验证
NP完全	NP-Complete	既在NP中又是NP-Hard的问题，NP中最难的问题
NP困难	NP-Hard	至少和NP中最难的问题一样难的问题，不一定是NP问题
非比较排序	Non-comparison Sort	不通过比较元素大小来排序的算法，如计数排序、基数排序，可突破O(n log n)下界

O

术语	英文	释义
在线算法	Online Algorithm	在不知道未来输入的情况下逐步做出不可撤销决策的算法
最优子结构	Optimal Substructure	问题的最优解包含子问题最优解的性质，是贪心和DP正确性的基础
0-1背包	0-1 Knapsack	每个物品只能选0或1个的背包问题，DP求解时间O(nW)，为伪多项式时间

P

术语	英文	释义
P类	Polynomial Time	确定性图灵机上多项式时间可解的判定问题类
Prim算法	Prim’s Algorithm	从任一顶点出发贪心扩展的最小生成树算法，二叉堆实现O(E log V)
快速排序	Quick Sort	分治排序算法，选择pivot分区后递归排序，平均O(n log n)，原地但不稳定
快速选择	Quickselect	在无序数组中找第k小元素，基于快速排序分区思想，平均O(n)

R

术语	英文	释义
基数排序	Radix Sort	按位排序的非比较算法，从最低位到最高位使用稳定排序，时间O(d(n+b))
递归树	Recursion Tree	将递推式展开为树形结构分析复杂度的直观工具
松弛	Relaxation	最短路径算法中的核心操作：若dist[u]+w(u,v)<dist[v]则更新dist[v]

S

术语	英文	释义
选择排序	Selection Sort	每轮选出最小元素放到已排序部分末尾的排序算法，时间O(n^2)，不稳定
Shell排序	Shell Sort	间隔递减的插入排序变体，间隔序列选择影响性能
稳定排序	Stable Sort	相等元素的相对顺序在排序后保持不变的排序算法
SPFA算法	Shortest Path Faster Algorithm	队列优化的Bellman-Ford，只对发生松弛的顶点邻接边松弛，平均O(E)
强连通分量	Strongly Connected Component	有向图中任意两点互相可达的极大子图，Tarjan算法O(V+E)求解
状态压缩DP	Bitmask DP	用整数二进制位表示集合状态，将多维状态压缩为一维的DP技术

T

术语	英文	释义
拓扑排序	Topological Sort	对DAG顶点线性排序使每条边(u,v)中u排在v之前，Kahn算法或DFS后序逆序
树	Tree	n个节点的有限集合，连通无环图，n个节点有n-1条边
二叉搜索树	BST	左子树所有值<根<右子树所有值的二叉树，查找/插入/删除平均O(log n)
字典树	Trie	多叉树结构用于字符串集合的高效前缀匹配，查找时间与字符串长度相关
Timsort	Timsort	Python和Java默认排序算法，结合归并排序和插入排序，最好O(n)最坏O(n log n)
旅行商问题	TSP	求经过所有城市恰好一次并返回起点的最短回路，NP-Hard问题

W

术语	英文	释义
无后效性	No Aftereffect	一旦状态确定，未来决策只依赖当前状态值而不依赖到达路径的性质

X

术语	英文	释义
小o符号	Little-o Notation	非紧上界符号，f(n)=o(g(n))表示f(n)的增长速率严格小于g(n)
小omega符号	Little-omega Notation	非紧下界符号，f(n)=omega(g(n))表示f(n)的增长速率严格大于g(n)

Y

术语	英文	释义
一致性哈希	Consistent Hashing	分布式系统中减少节点增减时数据迁移量的哈希方案
优先队列	Priority Queue	支持按优先级取出元素的抽象数据类型，通常用堆实现

Z

术语	英文	释义
时空权衡	Time-Space Tradeoff	算法设计中时间与空间此消彼长的关系，常见策略为以空间换时间
自底向上DP	Bottom-up DP	按依赖顺序填表消除递归开销的DP实现方式
并查集	Union-Find	支持合并集合和查询元素所属集合的数据结构，路径压缩加按秩合并接近O(1)
完全背包	Complete Knapsack	物品可无限选取的背包问题，内层循环从小到大
核算法	Accounting Method	摊还分析的一种方法，为不同操作分配不同摊还代价，用存款支付昂贵操作
势能法	Potential Method	摊还分析的一种方法，定义势能函数将数据结构状态映射为非负实数