OI中常见的数学符号

Ada ·

更新时间:2024-11-10

· 834 次阅读

整除/同余理论常见符号 1、整除符号

$x\ |\ y$ 。表示 x 整除 y，即 x 是 y 的因数。

2、取模符号

$x \ mod \ y$ 。表示 x 除以 y 得到的余数。

3、互质符号

$x \perp y$ 。表示 x 和 y 互质。

4、最大公约数

gcd(x, y)。在无混淆意义的时候，可以写作 (x, y)。

5、最小公倍数

lcm(x, y)。在无混淆意义的时候，可以写作 [x, y]。

数论常见符号 1、求和符号

$\sum$ 。表示满足特定条件的数的和。

2、求积符号

$\prod$ 。表示满足特定条件的数的积。

其他常见符号 1、阶乘符号

$!$ 。 $n!=1\times 2\times 3\times \cdots \times n$ 。特别规定： $0!=1$ 。

2、向下取整

$\left \lfloor x \right \rfloor$ 。表示小于等于 x 的最大整数。

3、向上取整

$\left \lceil x \right \rceil$ 。表示大于等于 x 的最小整数。

渐进符号

一般用于复杂度表示。

1、大 $\Theta$ 符号

对于给定的一个函数 g(n)， $f(n)=\Theta (g(n))$ ，当且仅当 0" class="mathcode" src="https://private.codecogs.com/gif.latex?%5Cexists%20c_%7B1%7D%2C%20c_%7B2%7D%2C%20n_%7B0%7D%3E%200" />，使得 $\forall n \geq n_{0}, 0 \leq c_{1}\cdot g(n) \leq f(n) \leq c2 \cdot g(n)$ 。

也就是说，如果函数 $f(n)=\Theta (g(n))$ ，那么我们能找到两个正数 $c_{1}, c_{2}$ ，使得 f(n) 被 $c_{1}\cdot g(n)$ 和 $c2 \cdot g(n)$ 夹在中间。

2、大 $O$ 符号

$\Theta$ 符号同时给了我们一个函数的上下界，如果我们只有一个函数的渐近上界的时候，我们使用 $O$ 符号。

对于一个给定的函数 g(n)，我们把它记作 $O(g(n))$ 。 $f(n)=O(g(n))$ ，当切仅当 $\exists c, n_{0}$ ，使得 $\forall n \geq n_{0}, 0 \leq f(n) \leq c \cdot g(n)$ 。

研究时间复杂度时，通常会使用 $O$ 符号，因为我们关注通常是程序耗时的上界，而不关心其耗时的下界。

3、大 $\Omega$ 符号

我们使用 $\Omega$ 符号来描述一个函数的渐近下届。

对于一个给定的函数 g(n)，我们把它记作 $\Omega (g(n))$ 。 $f(n)=\Omega (g(n))$ ，当切仅当 $\exists c, n_{0}$ ，使得 $\forall n \geq n_{0}, 0 \leq c \cdot g(n) \leq f(n)$ 。

4、小 $o$ 符号

如果说大 $O$ 符号相当于小于等于号，那么小 $o$ 符号就相当于小于号。

5、小 $\omega$ 符号

如果说大 $\Omega$ 符号相当于小于等于号，那么小 $\omega$ 符号就相当于小于号。

常见性质 $f(n)=\Theta (g(n))\Leftrightarrow f(n)=O(g(n))\wedge f(n)=\Omega (g(n))$ $f_{1}(n)+f_{2}(n)=O(max(f_{1}(n), f_{2}(n)))$ $f_{1}(n)\times f_{2}(n)=O(f_{1}(n)\times f_{2}(n))$ $\forall a \neq1, log_{a}n = O(log_{2}n)$