数据结构与算法

概述

程序=算法+数据结构
数据：所有能输入到计算机并被计算机程序所处理的符号总称
数据元素：描述数据的基本单位，可以是一条记录、一个节点等
数据项：数据元素是记录时，一个数据元素可由若干个数据项组成
数据对象：性质相同的数据元素的集合
数据类型：一个值的集合（取值范围）和定义的一组操作的总称，分为原子类型和结构类型
数据结构：数据的逻辑结构、物理结构和运算
结构：数据元素之间的关系
- 集合结构：数据元素除了同属于一个集合，无其他关系
- 线性结构：数据元素之间一对一的邻接关系
- 树形结构：数据元素之间一对多的关系
- 图状或网状结构：数据元素之间多对多的关系
逻辑结构：用抽象的数学模型来描述数据结构中的逻辑关系，是数据本身固有的，独立于计算机
物理结构：数据的逻辑结构在计算机内的存储表示（映像）
- 顺序存储结构：按逻辑顺序存入连续存储单元
- 链式存储结构：借助指示元素存储地址的指针
算法评价：正确性、可读性、健壮性（容错处理）、高效率与低存储量需求
时间复杂度：最基本语句的执行次数
空间复杂度：辅助变量所占空间

线性表

线性表：n个数据元素的有限序列
顺序表：线性表的顺序存储结构，用地址连续的存储单元存放一个线性表，可随机存取，但插入、删除操作平均移动 $\frac{n}{2}$ 个元素
链表：线性表的链式存储结构，插入、删除不需要移动数据，不需要预先分配空间，但只能顺序存取
- 头结点的数据域空闲或存放附加信息（如表长），指针域指向第一个数据元素，标识整个链表
- 单循环链表：只有一个指针域，尾结点指向头结点
- 双循环链表：有两个指针域，分别指向前驱和后继

队列

一端进入（rear）另一端删除（front）的线性表，先进先出
假溢出问题： $front\ne0,rear=M(最大空间)$
- 循环队列：使用模运算，入队 $rear=(rear+1)%M$ ，出队 $front=(front+1)%M$ ，判断队满：可以另设一个标志，也可以少用一个元素空间

栈

在表尾（栈顶）插入或删除的线性表，先进后出
顺序栈：用小下标做栈底（此时顺序存储结构不存在插入、删除需要移动数据的问题了）
链栈：栈顶节点为第一个节点
可实现递归到非递归的转化

数组

数组：线性表中数据元素本身也是一个线性表，一旦被定义则数据元素个数固定，不做插入删除操作，只有读取和更新
特殊矩阵的压缩存储：
- 对称矩阵（ $a_{ij}=a_{ji}$ ）：只存储主对角线和一半，压缩前元素 $n^2$ 个，压缩后 $n(n+1)/2$ 个
- 三角矩阵（一半的数相同）：压缩前元素 $n^2$ 个，压缩后 $n(n+1)/2+1$ 个，相同的元素只放一个到最后
- 对角矩阵（非零元素都集中在主对角线带状区域）：也是按行存放在一维数组b中
- 稀疏矩阵（非零元素少且无规律，系数因子 $\delta=\frac{t个非零元素}{m*n}\le0.05$ ）：使用三元组顺序表（记录行列值）、十字链表（每行每列都用单循环链表连接）只存储非零元素

广义表

广义表：数据元素既可以是原子项又可以是子表的线性表
广义表的深度：广义表中括号嵌套的最大数，原子深度为0，空表深度是1，递归表深度为无穷
表头：第一个元素
表尾：除去第一个元素组成的表

树

树：以分支关系定义的层次结构，有且仅有一个根结点，其余结点可分为多个互不相交的有限集，其本身又是一棵树（边数=节点数-1）
表示方法：图示法、广义表表示法、集合表示法、缩进表示法
结点的度：相连的孩子结点数，所有结点度的最大值称为树的度
叶子结点：度为0的结点，又称为终端结点
分支节点：度不为0的结点，也成为非终端结点（包括根结点）
特殊的树：
- 有序树：各子树从左到右有次序
- 有向树：边有方向，度为n时也称n元树
- 位置树：每个孩子结点位置不能改变的有向树，度为m时也称m叉树
- 森林：m棵互不相交的树的集合
二叉树的性质：
- 第i层最多有 $2^{i-1}$ 个结点
- 深度为k的二叉树最多有 $2^k-1$ 个结点
- 任意一个二叉树， $n_0=n_2+1$
满二叉树：每一层都是满的， $2^{i-1}$ 个结点
完全二叉树：各层都是满的，最底层从右起可以连续缺m个结点
- 深度： $[\log_2n]+1$
- 每行依次排序， $i$ 的双亲为 $[i/2]$ ，孩子结点分别为 $2i，2i+1$
- 编号大于 $[n/2]$ 的结点均为叶子结点
二叉树的存储：顺序存储（上到下、左到右存储在一维数组中，必要时可以增加虚节点），链式存储（二叉链表，两个指针域分别指向左右子树，一定有n+1个空指针域）
二叉树（链式）的遍历：
- 按层次遍历：按队列先进先出
- 递归遍历：先序遍历（根左右），中序遍历（左根右），后序遍历（左右根），可按堆栈先进后出
霍夫曼树：带权路径长度最短的树
- 结点间的路径长度：结点间路径的边数
- 树的路径长度：从根节点到每个结点的路径长度之和
- 结点的带权路径长度：结点权值乘以到根节点的路径长度
- 树的带权路径长度：所有叶子结点的带权路径长度之和
- 霍夫曼算法：递增排序，选择最小的两个当叶子结点，将二者之和当做权重继续排序选择

图

顶点的度：和顶点相连的边的数目，有向图中包括入度和出度
连通图：任意两个顶点都连通
连通分量：无向图中的极大连通子图
生成图：顶点相同，而边为原图的子集，若生成图为树，则叫生成树
图的顺序存储：邻接矩阵（唯一）
- 方阵，n维，1代表相连，0代表不连
- 无向图主对角对称，可压缩；而有向图不一定对称
- 某行（列）中1的个数即为顶点的度
- 可类似存储网，矩阵值则为权重
- 适合稠密图，复杂度 $O(n^2)$
图的链式存储：邻接表（不唯一）
- 顶点数组+n个临界点单链表（邻接点域+指针域）
- 适合稀疏图，复杂度 $O(n+e)$
图的遍历：
- DFS：递归过程，复杂度 $O(n+e)$
- BFS：非递归过程，需要队列暂存刚访问的顶点，复杂度 $O(n+e)$ ，找邻接点所需时间为 $O(e)$

查找

查找效率由数据的存储方式决定
顺序查找：可以在数组第一个位置设置监视哨（与被查找值相同），返回0则说明查找失败
- 查找成功的比较次数： $\frac{n+1}{2}$
- 查找失败的比较次数： $n+1$
- 适合顺序表和链表且不要求记录有序，不适合记录较多的时候
二分查找：要求按关键字域有序排列
- 查找成功（失败）的比较次数： $\log_2n$
- 顺序存储结构
分块查找：线性表分块，块内无序，块间有序，还需一个索引表
- 索引存储结构
动态查找表：查找过程中动态生成
二叉排序树：左子树均小于其根的关键字
- 树型查找：递归过程
- 平均查找时间：取决于树的深度，最坏情况下 $\frac{n+1}{2}$ ，最好情况下 $[\log_2n]+1$
平衡二叉树（AVL树）：每个结点左右子树深度之差绝对值 $\le1$ 的二叉排序树
散列表：实现关键字集合与表中位置映射
- 直接定址法：用线性函数，适合地址集合大小等于关键字集合大小
- 数学分析法：关键字已知且位数比散列地址位数大
- 平方取中法：适合不知道全部关键字
- 折叠法：适合关键字位数很多
- 随机数法
- 除留余数法：简单常用，合理原则除数
处理冲突：开放地址法（开放新的地址）、链地址法（用单链表存储）

人工智能基础

概述

机器学习算法：根据标签已知程度分为有监督学习、弱监督学习、无监督学习

聚类分析

聚类：无标签数据、无监督、寻找数据结构聚类
分类：有标签数据、监督、寻找分类边界
相似性测度：欧氏距离、马氏距离（考虑协方差，排除样本相关性，无量纲，当协方差为单位阵时马氏和欧式相同）、明氏距离（多维一般情况）、角度相似性函数（余弦）
分级聚类法：从n类开始逐步合并最相似的样本，停止条件可以是直到最后的k的类、设置最大类内距离门限等
Kmeans算法：先随机选取k个聚类中心，把样本分配给最近中心，最小化距离平方值和来更新聚类中心。缺点是依赖k值和初始值选取，适合球形
密度峰值聚类：根据距离阈值得到密度 $\rho_i$ $ρ_{i}$ ，计算比自己密度大的点最近距离 $\delta_i$ $δ_{i}$ ，得到 $\gamma_i=\rho_i \delta_i$ $γ_{i} = ρ_{i} δ_{i}$ ，根据设定的数量阈值得到聚类中心
- 类中心： $\rho$ 大， $\gamma$ 大
- 类中心附近： $\rho$ 大， $\gamma$ 小
- 坏点： $\rho$ 小， $\gamma$ 大
- 类中心边缘： $\rho$ 小， $\gamma$ 小

统计判别与概率密度估计

贝叶斯决策：已知类别的先验概率 $P(W_i)$ 及似然函数 $p(x/W_i)$ ，利用贝叶斯公式可得类别的后验概率 $P(W_i/x)$ ，再基于最小错误率准则或最小风险准则进行判决
- 最小错误率准则：哪种类别后验概率大，选哪个
- 最小风险准则：选择损失函数（选择0-1损失函数时与最小错误率一样）进行奖励或惩罚
概率密度估计：似然函数未知，用样本数据估计
- 类的概型已知，但参数未知：可以把参数当做非随机量处理（矩法估计、最大似然估计），或当做随机变量（贝叶斯估计等）
- 类的概型未知：总体推断（Parzen窗法、 $K_N$ 近邻估计、随机逼近法等）
矩法估计：只用于各阶矩的估计，对于原点矩的估计无偏，对于中心矩的估计是相合估计量，适合样本容量较大的情况
最大似然估计：最大化似然函数（N个随机样本取定值的联合概率密度，带参数），若是独立的，似然函数可以写成连乘的形式，取对数后变成连加，求极值即可

线性判别

多类情况判别：
- 对每一类都进行两类判别：使多个判别函数大于0,则无法判别；判别函数都为负则为不确定区域
- 对每两类采用两类判别：有M(M-1)/2个判别平面，判决区间增大，不确定区间减小
- 每一类都有一个判别函数：有M个判别平面，无不确定区间
Fisher线性判别：寻找投影方向是两均值向量投影后的标准化距离最大，柯西不等式知最大值为总离差矩阵的逆乘以均值向量的差。讲解
支持向量机（SVM）：寻找超平面进行分类，离超平面最近的就是支持向量。讲解
- 拉格朗日乘子法：转化为对偶问题
- 核技巧（ $(c+\vec{x_i} \cdot \vec{x_j})^2$ ）：直接使用高维点积结果计算，无需再扩充维度，c使得结果包含了低次项到高次项的和
- 高斯核函数（ $e^{-\gamma||\vec{x_i}-\vec{x_j}||^2}$ ）： $\gamma$ 越大，点间相似性要求越严格，越容易过拟合；利用泰勒展开，他的结果能体现无限维度数据高低项组合的特点，非常适合非线性分类问题
自适应增强（AdaBoost）：用许多弱分类器自适应加权构成一个强分类器
- 分类器权重： $\alpha _t = \frac{1}{2}\ln \frac{1-\varepsilon _t}{\varepsilon_t}$ ，误差越小，权重越大，重视可靠分类器
- 样本权重： $D_{t+1}(i)=\frac{D_t(i)exp[-\alpha_ty_ih_t(x_i)]}{Z_t}$ ，越差越大，权重越大，重视困难样本

深度学习

深度学习本质：通过深层次特征空间映射，深层结构能够实现更复杂的非线性拟合
卷积神经网络：
- 卷积层：数据的深度由滤波器数量决定，每一层的宽和高由滤波器的大小和步长决定
- 池化层：对卷积层的输出分块取最大值或均值，进行数据降维（宽和高），降低平移变形的敏感度，不易过拟合
- 激活层：使用非线性激活函数增加非线性拟合能力，sigmoid函数的广泛饱和性会使得基于梯度的学习变得困难
- 全连接层：拉成向量通过内积使每个输出与所有输入神经元连接
- 损失函数：交叉熵损失（标签为0,1）、铰链损失函数（-1,1）、指数损失函数
- 反向传播算法：通过链式求导法则和梯度下降法从尾到前实现参数的训练
梯度消失：对于sigmoid、tanh等激活函数导数值变为零，导致更新慢，难收敛
过拟合：训练误差小，验证误差大。原因：可调参数很多（自由度大）权重范围大、样本数量少，解决如下：
- 更换简单网络：数据集太简单而网络学习能力太强
- 权重衰减：加上惩罚项（通常为其范数），使模型参数足够小和平滑
- Dropout：随机选择神经元进行训练
- 正则化：对每一层结果进行尺度归一化，减小数据抖动，增加了收敛速度
AlexNet：
- 首次使用ReLU作为激活函数
- 提出LRN（归一化），加速收敛
- 采用数据增广避免过拟合
- 重叠池化
- 使用Dropout避免过拟合
GoogLeNet：
- 使用1乘1卷积进行降维，降低了卷积参数的数量
- 在多个尺寸上同时卷积再聚合
ResNet：
- 添加残差模块，在输入和输出间建立了连接，反传时增加了一项避免梯度为零
生成对抗网络GAN
- 同时训练生成模型和判别模型

附录

稀疏矩阵的十字链表表示

卷积神经网络架构

常用激活函数