数据结构与算法¶

本页补充堆、图存储、卷积神经网络和递归等基础概念。

二叉堆¶

二叉堆是满足堆序性质的完全二叉树，通常用数组存储。最小堆要求每个结点关键字不大于子结点，根结点是全局最小值；最大堆则相反。下标从 0 开始时，结点 i 的左、右孩子下标分别为 2i+1、2i+2，父结点下标为 floor((i−1)/2)。

插入元素时先放到数组末尾，再不断与父结点比较并上浮，时间复杂度 O(log n)；删除堆顶时用末尾元素补到根，再向下选择更优子结点下沉，时间复杂度 O(log n)；查看堆顶为 O(1)。从无序数组建堆可用自底向上的下沉法，复杂度为 O(n)。二叉堆适合实现优先队列，但不支持像平衡搜索树那样高效地查找任意关键字。

邻接矩阵¶

邻接矩阵用 n×n 矩阵 A 表示 n 个顶点之间的边：若顶点 i 到 j 有边，则 A[i][j] 记录 1 或边权，否则记录 0、无穷大或其他约定值。无向图的矩阵关于主对角线对称；有向图的矩阵不一定对称；带权图把边权放入矩阵。

邻接矩阵判断两点是否相邻为 O(1)，适合边较多的稠密图，也便于表示带权边和执行矩阵运算；但空间复杂度为 O(n²)，遍历某顶点所有邻接点需要 O(n)。稀疏图通常使用邻接表节省空间。无向图边数统计时要注意矩阵中的一条边会出现两次，不能把所有非零元素直接当作边数。

CNN 各层的作用¶

卷积神经网络（CNN）通过局部连接和权重共享提取具有空间结构的数据特征，常用于图像、视频和部分时序任务。

输入层：接收像素或特征张量，通常按高、宽、通道组织，并做归一化等预处理。
卷积层：用可学习卷积核在局部区域滑动并计算加权和，提取边缘、纹理、形状等局部模式；多个卷积核产生多个特征图。
激活层：对卷积结果施加 ReLU 等非线性函数，使网络能表达复杂非线性关系，并改善深层训练效果。
池化层：对局部区域做最大值或平均值汇聚，降低空间分辨率、压缩计算量并增强一定的平移鲁棒性；现代网络也常用步幅卷积替代部分池化。
归一化层：如 Batch Normalization，通过调整中间特征分布帮助训练稳定和加速收敛，具体位置依网络结构而定。
全连接层/分类头：整合高层特征，将其映射为类别得分、回归值或其他任务输出。
输出层：分类时常用 Softmax 得到多类概率，二分类可用 Sigmoid；损失函数把预测与标签的差异转化为训练目标。

不是每个 CNN 都必须包含所有层，网络结构会根据分类、检测、分割等任务调整。

递归与程序调用不是一回事¶

递归是函数或过程直接、间接调用自身的定义方式；程序调用是一个更一般的概念，表示调用者把控制权交给另一个函数或过程，执行结束后再返回。普通函数调用可以不递归，递归调用则必然包含函数调用。

一个正确的递归过程至少需要基准情形和递归情形：基准情形直接给出结果并停止继续调用；递归情形把问题缩小为更小的同类问题，并最终到达基准情形。每次调用都会在调用栈中保存参数、局部变量和返回位置，因此递归过深可能栈溢出，重复子问题还可能造成指数级时间。若能用循环或显式栈保存状态，可将递归改写为迭代形式，但要保持相同的终止条件和状态转移。

来源：补充知识点1.md

考前易错速记¶

二分查找时间复杂度为 O(log n)，哈希查找平均 O(1)，快速排序平均 O(n log n)。B+ 树适合数据库索引和范围查询；哈希索引适合等值查找，通常不适合范围查询。

广义表是线性表的推广，元素可以是原子或子表；长度是最外层元素个数，深度是括号最大嵌套层数。表头是第一个元素，表尾是其余元素组成的表，因此表尾仍然是表。

来源：专业课速记/09_考前必背清单.md