算法基础
排序算法：
- 插入算法：从前向后遍历，按顺序插入元素
- 希尔排序：类似插入排序，但是遍历元素过程中存在间隔，减少了插入排序的元素移动次数
- 冒泡排序：类似插入算法，但数据更加相邻
- 选择排序：依次取出最小元素
- 归并排序：递归拆分数组，拆分后一层层合并。分治策略，简化问题
- 堆排序：将数组构建成小根堆，依次取出堆顶元素并更新小根堆
- 快速排序：取出最左侧元素，从右向左查找，若查找的元素小于当前元素则交换位置，并变更查找方向。一次遍历后效果为比当前元素小的在左边，反之在右边，递归进行
- 计数排序：桶思想，每个值对应一个桶，桶内数据存在多个
- 桶排序：每个桶存储一段范围，桶内使用简单的排序算法
- 基数排序：依次按个位、十位、百位排序，避免数据不均匀问题
基础查找算法：
- 顺序查找：适用无序数据结构，其它方法均要求有序
- 二分查找：适用于数组、二叉树
- 插值查找：类似二分查找，但是通过启发式的公式计算拆分点
- 分块查找：类似桶排序的查找思路，先分块再查找，适用于数组、桶、多叉树
字符串查找：
- 暴力逐个字符匹配
- KMP算法：利用字符串的前缀特征加速比较，复杂度稳定
- Boyer-Moore算法：利用字符串后缀特征、字符出现位置加速比较，一般情况下性能更好
- Sunday算法：利用字符出现位置加速比较，在被查找字符串较短时存在优势
- Rabin-Karp算法：将字符串压缩为hash值再比较，对hash策略有较高要求，适合同时查找多个子串
图算法：
- 广度优先搜索（BFS）
- 深度优先搜索（DFS）
- A*算法：启发式搜索算法，使用某个公式计算下一步应该查找哪个节点
- Dijkstra算法：查找从某个节点到另一节点的最短路径。贪心搜索最近节点
- Bellman-Ford算法：查找从某个节点到另一节点的最短路径，支持负权边。遍历所有节点
- Floyd-Warshall算法：统计任意两点间的最短路径。使用临接矩阵与状态转移的思路实现，类似Bellman-Ford算法
- Prim算法：将图转换为最小生成树的算法，类似Dijkstra算法
- 匈牙利算法：二分图算法
差错检测：
- 奇偶校验：计算每段数据中bit值为1的数量
- 校验和：简单的字节累加
- 块和校验：对数据块逐行逐列进行奇偶校验
- 循环冗余校验（CRC）：对数据取模，更标准常用，检查的错误类型更多
- 汉明校验码：块和校验的优化版本，提高校验效率
- 哈希函数：MD5、SHA-1、SHA-256
操作系统
计算机组成原理
计算机网络
计算机图形学
- 抗锯齿优化方案
SSAA：超采样抗锯齿，等同于UE中调整屏幕百分比
FXAA：快速近视抗锯齿，对渲染后的图片边缘进行模糊平滑处理，可能导致高频信号丢失
MSAA：多采样抗锯齿，光栅化阶段在物体的边缘进行超采样
TAA：时间抗锯齿，结合前后多帧的采样，并修正物体移动的影响
SMAA：子像素形态抗锯齿，类似FXAA进行边缘模糊处理，但是通过更复杂的算法对边缘进行更准确的识别，避免整体效果模糊的问题
DLSS：深度学习上采样，通过AI完成抗锯齿。这个功能不只是抗锯齿，重点是上采样
- 近岸波浪曲线：
参数定义：$ A=2; B_0=2; B_1=5; $
波的前半部分与后半部分：$ F_a=x^A; F_b=(\frac{x-1}{B_1-1}-1)^{B_0};$
通过分段函数组合为完整的函数：$ F_c={x<=1:F_a(x), 1<x:F_b(x)}$
改造为最终的周期函数：$ F_d = F_c(mod(x,B_1)) $ - 线或线段是否相交：判断点是否在线的两侧(叉乘结果同号)
- Point In Polygon(PIP问题)：判断点是否在平面图形内
- 光线投射算法：先判断点是否在多边形包围框内，再判断点是否在多边形上。从点作为启动，取多边形上两点的中点作为射线目标方向，注意多边形上取的两点不得与起点共线。若射线与多边形有奇数个交点，则证明在多边形内。
- 回转数算法：逐个顶点按顺序遍历，记录遍历过程中点与当前顶点到点与下一个顶点的夹角，夹角总和为0时点在多边形外，2π时在多边形内。角度计算开销很高。
- 凸多边形：按照顺时针或逆时针，判断点是否在所有边的同一侧(叉乘结果同号)。
- 多边形内缩或外扩算法
- Delaunay三角剖分算法: 将点连接成3角面
- 其它算法查看《UE/引擎目录/Runtime/更详细的文件解析/FMath相关函数.md》
神经网络
最小化问题：
- 梯度下降算法：从某个自变量开始，查找函数局部最小值，不断向因变量减小的方向迭代自变量
回归：
线性回归：通过直线方程拟合自变量与因变量之间的关系。一种典型的监督学习方法，使用均方差等指标作为损失函数，使用梯度下降等算法作为优化算法。
一元线性回归：最简单的线性回归形式，一个自变量一个因变量
多元线性回归：多个自变量共同影响一个因变量，存在多重共线性、异常值、非线性关系、自相关等多种工程挑战
其它
- Halton：伪随机数生成算法，具有较强的均匀性质，生成多维数据是，建议采用不同基数
- RSA算法：非对称加密算法，若数据使用公钥加密，则除暴力破解外只能使用私钥解密，反之亦然
插值
- 线性插值：前后两个点之间使用线性系数进行插值
- 曲线插值：前后两个点之间使用曲线系数进行插值
- 多项式插值：利用前后多个点拟和多项式曲线，再在多项式曲线采样
- 其它拟和曲线插值：利用贝塞尔、样条线等方法拟和曲线并采样
- 双线性插值：对于多维度数据，需要在多个方向上进行插值，再对多个方向插值的结果进行插值。共需要n+n-1+n-2+ … +1次
- DLSS超分辨率：深度学习超级采样
- 帧生成/插帧：基于光流等属性判断像素两帧间移动的方向与距离，对前后两帧进行插值
平滑
移动平均：取最新的多个点进行平均。可以对最新点进行加权。称为加权移动平均
二次移动平均：普通的平均方法在快速增长或减小的曲线上存在数据误差，可以对数据的斜率进行平均
滤波：均值滤波、高斯滤波、中值滤波等。
电容电感：平滑电压，按照指数曲线渐进