前言

虽然叫名词解释，但是我做的事并不是解释名词，而是告诉大家一些关于这些名词的一些事。

当然可能有的不是名词，但也没有什么关系。

按照领域划分，因为有些东西要一起讲。

我会尽量的用专业的东西来说明，如果有错误，请指出，这非常重要，谢谢大家了。

基础算法

快速排序

• 快速排序 的时间复杂度为 \(O(n^2)\)。

C++ std::sort

• C++ 的 std::sort 的时间复杂度为 \(O(n\log n)\)。

二分和分治

• 二分查找（binary search，简称：二分），是用来在一个有序数组中查找某一元素的算法。

• 分治算法 的核心思想是“分而治之”。

字符串

前缀

• 前缀（prefix）是指从串首开始到某个位置 \(i\) 结束的一个特殊子串。字符串 \(S\) 的从 \(i\) 开头的后缀表示为 \(\operatorname{Prefix}(S, i)\)，也就是 \(\operatorname{Prefix}(S, i) = S[0.. i]\)。

• 真前缀 指除了 \(S\) 本身的 \(S\) 的前缀。

后缀

• 后缀（suffix）是指从某个位置 \(i\) 开始到整个串末尾结束的一个特殊子串。字符串 \(S\) 的从 \(i\) 开头的后缀表示为 \(\operatorname{Suffix}(S, i)\)，也就是 \(\operatorname{Suffix}(S, i) = S[S..\left | S \right | - 1]\)。

• 真后缀 指除了 \(S\) 本身的 \(S\) 的后缀。

数学

图形的边界

• 边界，指只看平面内的一个图形和另一个图形，所有满足以一个点为圆心画圆，不管以什么样的半径画圆圆内总会出现两个图形的点的集合。

复数

• 复数 的名称由 复杂的数 而来。

快速傅里叶变换

• 快速傅里叶变换（Fast Fourier Transform)，即利用计算机计算离散傅里叶变换（DFT）的高效、快速计算方法的统称，简称 FFT。快速傅里叶变换是 1965 年由 J.W.库利 和 T.W.图基 提出的。

牛顿分形

• 牛顿分形 虽然叫牛顿分形，但实际上牛顿并不知道牛顿分形。

图论

树

• 完整二叉树（full / proper binary tree）：每个结点的子结点数量均为 \(0\) 或者 \(2\) 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。

• 完全二叉树（complete binary tree）：只有最下面两层结点的度数可以小于 \(2\)，且最下面一层的结点都集中在该层最左边的连续位置上。

• 完美二叉树（perfect binary tree，或：满二叉树）：所有叶结点的深度均相同的二叉树称为完美二叉树。

差分约束

• 差分约束系统 是一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：

\[\begin{cases} x_{c_1} - x_{c^{'}_1} \leq y_1 \\ x_{c_2} - x_{c^{'}_2} \leq y_2 \\ \cdots \\ x_{c_m} - x_{c^{'}_m} \leq y_m \end{cases} \]

的不等式组（\(y_1, y_2, \cdots, y_m\) 已知）。

• 差分约束算法 是求解差分约束系统的一个算法。