Python 算法与蓝桥杯 Glossary
这门课讲的是：把一个实际问题变成"能算"的形式（建模），选一种数据组织方式与一套步骤去算它（数据结构与算法），并判断它在题目的数据规模和时限下算不算得完（复杂度）。术语表里前六个词是整门课的骨架——后面每一课都在用它们。
两节都算这门课的规范用词：课件正文与配图用词以本文件为准。开课时先把主题词写进「待掌握」，
学生真的会用之后挪进「已掌握」——挪动本身就是一条学习记录。
待掌握
算法:
解决某一类问题的一套有限、确定的步骤：给定合法输入，按步骤执行必然在有限步内停下并产出结果。
Avoid: 解法、方法、思路（想说"这道题的算法"时不要简写成"方法"，它和"函数/方法"会混）
数据结构:
数据在内存里的组织方式，以及在这种组织上允许做的操作（增、删、查、改）与各操作的代价。它决定了哪些操作便宜、哪些昂贵。
Avoid: 容器、存储结构、数据类型（list 是数据结构的一种实现，但"数据类型"指值的种类，不是组织方式）
时间复杂度:
算法执行的基本操作次数随输入规模 n 增长的趋势，用大 O 记号表示上界，如 O(n)、O(n log n)、O(n²)。它衡量增长趋势，不是秒数。
Avoid: 运行时间、耗时、速度（"时间复杂度"不是"跑了多久"，同一算法换台机器跑，复杂度不变）
大 O 记号:
描述函数增长速度的记号：O(g(n)) 表示"当 n 足够大时，增长不超过 g(n) 的常数倍"，因此只保留最高阶项、丢掉常数系数。
Avoid: 复杂度（大 O 是记号，复杂度是被描述的对象；也不要把 O 当成"精确等于"）
空间复杂度:
算法在计算过程中额外占用的存储量随输入规模 n 增长的趋势（通常不计输入本身占的空间）。
Avoid: 内存占用、内存消耗（不带"随 n 增长"这层意思时是另一回事）
数据规模:
题目输入中决定计算量的那个数量（n 个元素、n 个点、m 条边……），通常由题目给出的范围确定，是估算复杂度上限的起点。
Avoid: 数据量、大小、输入大小
均摊:
把偶尔一次的大开销平摊到很多次操作上，摊下来每次仍是 O(1)。比如列表 append：多数时候只往末尾空位写，偶尔扩容才搬动整块元素，所以是 O(1) 均摊而不是每次都快。
Avoid: 平均、大约（"均摊"指的是"一次性大开销被很多次便宜操作分摊"这个确定的事实，不是"平均大概 O(1)"这种模糊说法，也不能省掉"均摊"二字直接说成绝对 O(1)）
对拍:
把两个程序（通常是暴力解与候选解）跑在同一批随机输入上、比较输出是否一致，用来在没有标准答案时验证正确性的做法。
Avoid: 测试、比对、验证（它特指"两个程序互相比对"，不是泛指的测试）
暴力解:
不做任何优化、按定义直接枚举所有可能并检查的解法。它正确性容易保证但复杂度往往过高，常用来当对拍的参照。
Avoid: 朴素解、傻办法（想说"按定义直接做"时统一用"暴力解"）
递归:
函数在执行过程中直接或间接调用自身、把问题化为规模更小的同类问题的解法。必须存在不再递归的基准情形，否则无限递归。
Avoid: 迭代、循环（迭代是"重复执行"，不调用自身；两者可以互相改写但不是同一个词）
栈:
只允许在同一端插入和删除的线性结构，遵循后进先出。函数调用、括号匹配、深度优先搜索都靠它。
Avoid: 堆（堆是另一种结构，见下一条；"堆栈"这个混称在本课程里不用）
队列:
只允许一端插入、另一端删除的线性结构，遵循先进先出。广度优先搜索靠它。
Avoid: 栈、缓冲区（"缓冲区"太泛，指代不清时一律用"队列"）
堆:
一种能高效取出当前最小（或最大）元素的树形结构；Python 标准库 heapq 提供的是最小堆，只能保证堆顶最小、其余元素无序。
Avoid: 堆栈、优先队列（"优先队列"是它支持的抽象操作，本课程统一说"堆"；堆栈是错词）
哈希表:
通过哈希函数把键映射到存储位置、从而让按键查找平均代价与元素个数无关的结构。Python 的 dict 与 set 是它的实现，平均 O(1) 查找；最坏情况会退化。
Avoid: 字典、映射表（"字典"专指 Python 的 dict 这个具体类型；讲结构本身时说"哈希表"）
哈希冲突:
两个不同的键被哈希函数算到了同一个存储位置。冲突的键要顺着往下逐个比较才能区分，冲突越多越慢——这就是哈希表"平均 O(1)、最坏 O(n)"里那个最坏情况的来源。
Avoid: 碰撞、重复键（"重复键"指同一个键出现两次，是另一回事）
动态规划:
把问题拆成互相重叠的子问题，先算小规模、把结果存下来避免重复计算，再由子问题的答案组合出原问题的答案。使用它的前提是最优子结构与无后效性。
Avoid: 递推、记忆化搜索（记忆化搜索是它的实现方式之一，不是同义词；"递推"只描述计算顺序）
排序:
把一组元素按某个比较标准重新排成有序序列的操作。它是很多算法的前置步骤（有序之后才能二分、才能用双指针、才能贪心），也常直接就是答案。
Avoid: 分类、排列（"排列"指元素的不同顺序本身，不是"把序列排好"这个操作）
二分查找:
在一个有序序列上，每轮比较中间元素、据此丢弃一半区间的查找方法，代价 O(log n)。它成立的前提是"目标一定落在被保留的那一半里"。
Avoid: 折半查找、二分（单独说"二分"时先确认指的是查找还是"二分答案"；两者前提不同）
二叉树:
每个节点最多有两个子节点的树形结构。节点的左右孩子有顺序之分，因此左右互换是两棵不同的二叉树。
Avoid: 树、二叉搜索树（"树"是更一般的结构；"二叉搜索树"额外要求左小右大，是二叉树的一种，不是同义词）
广度优先搜索:
从起点开始一圈一圈向外扩、先访问所有距离为 1 的节点、再访问距离为 2 的，用队列实现。在无权图上第一次到达某个点的路径就是最短路径。
Avoid: BFS、广搜、层序遍历（"层序遍历"是它在树上的特例；正式行文写"广度优先搜索"，代码与图注里可用 BFS）
深度优先搜索:
从起点沿一条路一直走到底、走不动了再回退到上一个岔口换一条路，用栈（或递归）实现。它天然对应回溯，搜到的第一条路不保证最短。
Avoid: DFS、深搜、递归（递归只是它的实现方式，不是它本身；正式行文写"深度优先搜索"，代码与图注里可用 DFS）
图的表示:
把图存进程序里的方式，主要有两种：邻接矩阵用二维表记录每对点之间有没有边（查边 O(1)、占 O(n²) 空间）；邻接表给每个点记一张邻居清单（占 O(n+m) 空间、遍历一个点的全部邻居快）。稀疏图用邻接表，稠密图或需要快速查边时用邻接矩阵。
Avoid: 存图、图的存储（想说这两种具体方式时统一写"邻接矩阵"与"邻接表"）