符号

描述

$\mathbb{N}$

自然数集

$\mathbb{Z}$

整数集

$ℝ$

实数集

${\mathbb{Z}}_q$

商环，并且为 $\left(-q/2,q/2\right]\cap \mathbb{Z}$ ，其中 $q\in \mathbb{Z}$ ，且 $q\ge 2$

$\log (\cdot )$

对数，且底为2

$\lceil \cdot \rceil$

向上取整

$〚\cdot 〛$

四舍五入

$a$

向量，且为列向量形式

$a^{\text{T}}$

向量 $a$ 的转置

$A$

矩阵， $A$ 亦可看作其列向量的有序集合 $\left\{a_1,a_2,\dots \right\}$

$A^{\text{T}}$

矩阵 $A$ 的转置

$\otimes$

张量积

$\Vert a\Vert$

向量 $a$ 的Euclidean范数，定义为 $\Vert a\Vert ={\left({\displaystyle {\sum }_i{\left|a_i\right|}^2}\right)}^{\frac{1}{2}}$ ，其中 $a_i$ 是向量 $a$ 的分量

$\Vert A\Vert$

矩阵 $A$ 的Euclidean范数，定义为 $\Vert A\Vert ={\max }_j\Vert a_j\Vert$ ，其中 $a_j$ 是矩阵 $A$ 的列向量

${\Vert a\Vert }_{\infty }$

向量 $a$ 的 $\infty$ 范数，定义为 ${\Vert a\Vert }_{\infty }={\max }_i\left|a_i\right|$ ，其中 $a_i$ 是向量 $a$ 的分量

${\Vert A\Vert }_{\infty }$

矩阵 $A$ 的 $\infty$ 范数，定义为 ${\Vert A\Vert }_{\infty }={\max }_{i,j}\left|a_{i,j}\right|$ ，其中 $a_{i,j}$ 是矩阵 $A$ 的元素

$\tilde{T}$

向量集合 $T$ 的Gram-Schmidt正交化

$O,o,\Omega ,\omega$

算法渐近符号

$\text{poly}\left(n\right)$

$f\left(n\right)$ ，且对某一常数c，使得 $f\left(n\right)=O\left(n^c\right)$

$\text{negl}\left(n\right)$

$f\left(n\right)$ ，且对每一固定常数c，都使得 $f\left(n\right)=o\left(n^{-c}\right)$