信息学奥赛常用数学符号
欢迎来到信息学奥赛常用数学符号教程！在信息学竞赛（如NOIP, CSP, NOI等）中，扎实的数学基础是解决算法问题的关键。许多题目描述和解题思路都离不开特定的数学符号。
本教程旨在系统地介绍这些常用符号，包括它们的**含义、读法、常见用法以及在算法中的应用**。通过清晰的讲解、直观的示例和互动练习，帮助你快速掌握这些重要的数学工具，提升解题能力。
点击下方卡片开始学习吧！👇
📚 课程目录
📊 信息学奥赛数学符号总览
下表汇总了信息学奥赛中最常遇到的数学符号，按照常见领域进行了分类。你可以用它来快速回顾或查找特定符号的含义。
| 符号 | 中文名称 | 英文名称 | 意义 / 用法 | 常见公式示例 |
|---|---|---|---|---|
| 集合符号 | ||||
| $ \in $ | 属于 | Element of | $ a \in A $ 表示 $a$ 是集合 $A$ 的元素 | $ 2 \in \{1, 2, 3\} $ |
| $ \notin $ | 不属于 | Not element of | $ a \notin A $ 表示 $a$ 不是集合 $A$ 的元素 | $ 4 \notin \{1, 2, 3\} $ |
| $ \subseteq $ | 子集 | Subset | $ A \subseteq B $ 表示 $A$ 是 $B$ 的子集（允许 $A=B$） | $ \{1, 2\} \subseteq \{1, 2, 3\} $ |
| $ \subset $ | 真子集 | Proper subset | $ A \subset B $ 表示 $A$ 是 $B$ 的子集且 $A \neq B$ | $ \{1, 2\} \subset \{1, 2, 3\} $ |
| $ \cup $ | 并集 | Union | $ A \cup B $ 包含所有 $A$ 或 $B$ 中的元素 | $ \{1, 2\} \cup \{2, 3\} = \{1, 2, 3\} $ |
| $ \cap $ | 交集 | Intersection | $ A \cap B $ 包含所有同时在 $A$ 和 $B$ 中的元素 | $ \{1, 2\} \cap \{2, 3\} = \{2\} $ |
| $ \setminus $ | 差集 | Difference / Set minus | $ A \setminus B $ 包含所有在 $A$ 中但不在 $B$ 中的元素 | $ \{1, 2, 3\} \setminus \{2, 3\} = \{1\} $ |
| $ |A| $ | 集合大小 | Cardinality | 集合 $A$ 中元素的个数 | $ |\{1, 2, 3\}| = 3 $ |
| $ \emptyset $ 或 $ \{\} $ | 空集 | Empty set | 不包含任何元素的集合 | $ A \cap \emptyset = \emptyset $ |
| 数论符号 | ||||
| $ a \mid b $ | 整除 | Divides | $b$ 可以被 $a$ 整除 ($a \neq 0$) | $ 3 \mid 12 $ |
| $ a \nmid b $ | 不整除 | Does not divide | $b$ 不能被 $a$ 整除 | $ 5 \nmid 12 $ |
| $ \text{mod} $ | 取模 | Modulo | $ a \pmod b $ (或 $a \bmod b$) 是 $a$ 除以 $b$ 的余数 | $ 7 \bmod 3 = 1 $ |
| $ \equiv $ | 同余 | Congruent | $ a \equiv b \pmod m $ 表示 $a$ 和 $b$ 除以 $m$ 的余数相同 | $ 7 \equiv 1 \pmod 3 $ |
| $ \text{gcd}(a, b) $ | 最大公约数 | Greatest Common Divisor | $a$ 和 $b$ 的最大正公约数 | $ \text{gcd}(12, 18) = 6 $ |
| $ \text{lcm}(a, b) $ | 最小公倍数 | Least Common Multiple | $a$ 和 $b$ 的最小正公倍数 | $ \text{lcm}(4, 6) = 12 $ |
| $ \phi(n) $ | 欧拉函数 | Euler's totient function | 小于等于 $n$ 且与 $n$ 互质的正整数个数 | $ \phi(6) = 2 $ (1, 5) |
| 代数与组合符号 | ||||
| $ \sum $ | 求和 | Summation | 对一系列项求和 $ \sum_{i=a}^{b} f(i) $ | $ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} $ |
| $ \prod $ | 连乘 | Product | 对一系列项求积 $ \prod_{i=a}^{b} f(i) $ | $ \prod_{i=1}^{n} i = n! $ |
| $ n! $ | 阶乘 | Factorial | $ n! = 1 \times 2 \times \dots \times n $ ($0! = 1$) | $ 5! = 120 $ |
| $ C(n, k) $ 或 $ \binom{n}{k} $ | 组合数 | Combination / Binomial coefficient | 从 $n$ 个不同元素中选 $k$ 个的方案数 | $ C(n, k) = \frac{n!}{k!(n-k)!} $ |
| $ P(n, k) $ 或 $ A_n^k $ | 排列数 | Permutation | 从 $n$ 个不同元素中选 $k$ 个进行排列的方案数 | $ P(n, k) = \frac{n!}{(n-k)!} $ |
| $ \log_b a $ | 对数 | Logarithm | 以 $b$ 为底 $a$ 的对数 | $ \log_2 8 = 3 $ |
| $ \lg n $ | 常用对数/以2为底 | Log base 10 / Log base 2 | 信息学中常指 $ \log_2 n $ | 算法复杂度 $ O(n \lg n) $ |
| $ \ln n $ | 自然对数 | Natural logarithm | 以 $e$ 为底的对数 $ \log_e n $ | 微积分中常见 |
| 逻辑符号 | ||||
| $ \land $ | 与 (合取) | And (Conjunction) | $ p \land q $ 为真，当且仅当 $p, q$ 都为真 | $ (x>0) \land (x<5) $ |
| $ \lor $ | 或 (析取) | Or (Disjunction) | $ p \lor q $ 为真，当且仅当 $p, q$ 至少一个为真 | $ (n \% 2 == 0) \lor (n \% 3 == 0) $ |
| $ \neg $ 或 $ \sim $ | 非 (否定) | Not (Negation) | $ \neg p $ 为真，当且仅当 $p$ 为假 | $ \neg (x = 0) $ 等价于 $ x \neq 0 $ |
| $ \Rightarrow $ 或 $ \rightarrow $ | 蕴含 (推出) | Implies | $ p \Rightarrow q $ 表示若 $p$ 为真，则 $q$ 必为真 | $ x > 2 \Rightarrow x^2 > 4 $ |
| $ \Leftrightarrow $ 或 $ \leftrightarrow $ | 等价 (当且仅当) | Equivalent (If and only if) | $ p \Leftrightarrow q $ 表示 $p, q$ 同真同假 | $ (x=2) \Leftrightarrow (x^2=4 \land x>0) $ |
| $ \forall $ | 任意 (全称量词) | For all | 对所有... | $ \forall x \in \mathbb{R}, x^2 \ge 0 $ |
| $ \exists $ | 存在 (存在量词) | Exists | 存在至少一个... | $ \exists x \in \mathbb{Z}, x^2 = 4 $ (x=2 或 x=-2) |
| 复杂度符号 | ||||
| $ O(f(n)) $ | 大O (渐进上界) | Big-O | 函数增长率的上界 | 排序算法 $ O(n \log n) $ |
| $ \Omega(f(n)) $ | 大Omega (渐进下界) | Big-Omega | 函数增长率的下界 | 基于比较的排序 $ \Omega(n \log n) $ |
| $ \Theta(f(n)) $ | 大Theta (渐进紧确界) | Big-Theta | 函数增长率的精确界 ($O$ 且 $\Omega$) | 归并排序 $ \Theta(n \log n) $ |
| $ o(f(n)) $ | 小o (非紧确上界) | Little-o | 严格小于 $f(n)$ 的增长率 | $ n = o(n^2) $ |
| $ \omega(f(n)) $ | 小Omega (非紧确下界) | Little-omega | 严格大于 $f(n)$ 的增长率 | $ n^2 = \omega(n) $ |
| 其他常用符号 | ||||
| $ \lfloor x \rfloor $ | 向下取整 (地板函数) | Floor function | 小于或等于 $x$ 的最大整数 | $ \lfloor 3.7 \rfloor = 3 $, $ \lfloor -3.2 \rfloor = -4 $ |
| $ \lceil x \rceil $ | 向上取整 (天花板函数) | Ceiling function | 大于或等于 $x$ 的最小整数 | $ \lceil 3.2 \rceil = 4 $, $ \lceil -3.7 \rceil = -3 $ |
| $ \infty $ | 无穷大 | Infinity | 表示无限大的概念 | $ \lim_{n \to \infty} \frac{1}{n} = 0 $ |
| $ \approx $ | 约等于 | Approximately equal | 数值上近似相等 | $ \pi \approx 3.14159 $ |
| $ \propto $ | 正比于 | Proportional to | $ y \propto x $ 表示 $ y = kx $ (k为常数) | 动能 $ E_k \propto v^2 $ |
| $ \mathbb{N} $ | 自然数集 | Natural numbers | 通常指 $ \{0, 1, 2, \dots\} $ 或 $ \{1, 2, 3, \dots\} $ (注意定义) | $ n \in \mathbb{N} $ |
| $ \mathbb{Z} $ | 整数集 | Integers | $ \{\dots, -2, -1, 0, 1, 2, \dots\} $ | $ x \in \mathbb{Z} $ |
| $ \mathbb{Q} $ | 有理数集 | Rational numbers | 可以表示为 $ p/q $ 的数 ($p, q \in \mathbb{Z}, q \neq 0$) | $ \frac{1}{2} \in \mathbb{Q} $ |
| $ \mathbb{R} $ | 实数集 | Real numbers | 包括有理数和无理数 | $ \pi \in \mathbb{R} $ |
注意: 某些符号 (如 $ \lg n $, $ \mathbb{N} $) 的具体含义可能因上下文或约定而略有不同，请留意题目说明或通常惯例。
∪ 集合符号
集合是数学的基本概念，表示一些具有共同性质的事物的总体。信息学中常用集合来描述元素的归属、关系和操作。
含义: 表示一个元素是某个集合的成员。
读法: "属于" 或 "is an element of"。$a \in S$ 读作 "a 属于 S"。
反义: $ \notin $ (不属于)。
示例:
$ 5 \in \{1, 3, 5, 7\} $ (5 属于集合 {1, 3, 5, 7})
$ 4 \notin \{1, 3, 5, 7\} $ (4 不属于集合 {1, 3, 5, 7})
含义: $A \subseteq B$ 表示集合 $A$ 中的所有元素都在集合 $B$ 中。
注意: 允许 $A = B$。
相关: $ \subset $ (真子集)，表示 $A \subseteq B$ 且 $A \neq B$。
示例:
$ \{1, 2\} \subseteq \{1, 2, 3\} $ (是子集)
$ \{1, 2, 3\} \subseteq \{1, 2, 3\} $ (是子集)
$ \{1, 2\} \subset \{1, 2, 3\} $ (是真子集)
$ \{1, 4\} \not\subseteq \{1, 2, 3\} $ (不是子集)
含义: $A \cup B$ 是包含所有 $A$ 中或 $B$ 中元素的新集合（重复元素只计一次）。
类比: 逻辑 "或" ($\lor$)。
示例:
$ \{1, 2\} \cup \{2, 3\} = \{1, 2, 3\} $
$ A = \{a, b\}, B = \{c, d\} \Rightarrow A \cup B = \{a, b, c, d\} $
含义: $A \cap B$ 是包含所有同时存在于 $A$ 和 $B$ 中的元素的新集合。
类比: 逻辑 "与" ($\land$)。
示例:
$ \{1, 2\} \cap \{2, 3\} = \{2\} $
$ \{1, 2\} \cap \{3, 4\} = \emptyset $ (空集)
含义: $A \setminus B$ (或 $A - B$) 是包含所有在 $A$ 中但不在 $B$ 中的元素的新集合。
注意: 运算顺序很重要，$A \setminus B \neq B \setminus A$ (除非 $A=B$)。
示例:
$ \{1, 2, 3\} \setminus \{2, 3\} = \{1\} $
$ \{2, 3\} \setminus \{1, 2, 3\} = \emptyset $
含义: 表示集合 $A$ 中元素的数量。
应用: 容斥原理、计数问题等。
示例:
$ S = \{a, b, c\} \Rightarrow |S| = 3 $
$ |\emptyset| = 0 $
容斥原理: $|A \cup B| = |A| + |B| - |A \cap B|$
≡ 数论符号
数论研究整数的性质，在信息学竞赛中非常重要，尤其是在密码学、组合计数和优化问题中。
含义: $ a \pmod b $ (或 $ a \bmod b $, C++/Java中用 `%` 运算符) 表示 $a$ 除以 $b$ 的非负余数。
范围: 通常结果在 $[0, b-1]$ 区间内（对于正数 $b$）。注意负数的取模在不同语言中可能不同。
应用: 哈希、大数运算、周期性问题、同余。
示例:
$ 17 \bmod 5 = 2 $ (因为 $17 = 3 \times 5 + 2$)
$ 10 \bmod 2 = 0 $ (10是偶数)
$ -7 \bmod 3 $ 在数学上通常是 $2$, 但 C++/Java 中可能是 $-1$ (依赖实现)。通常用 `(a % b + b) % b` 来确保正余数。
含义: $ a \equiv b \pmod m $ 表示 $a$ 和 $b$ 除以 $m$ 的余数相同。
等价条件: $ m \mid (a-b) $，即 $m$ 能整除 $a-b$ 的差。
性质: 同余关系具有类似等号的性质（反射性、对称性、传递性），可以进行加、减、乘运算。
示例:
$ 17 \equiv 2 \pmod 5 $ (因为 $17 \bmod 5 = 2$ 且 $2 \bmod 5 = 2$)
$ 10 \equiv 0 \pmod 2 $
$ -1 \equiv 4 \pmod 5 $ (因为 $5 \mid (-1 - 4)$)
应用: 费马小定理、欧拉定理、中国剩余定理。
含义: $\text{gcd}(a, b)$ (Greatest Common Divisor) 是能同时整除 $a$ 和 $b$ 的最大正整数。
算法: 常用欧几里得算法（辗转相除法）高效计算。
性质: $\text{gcd}(a, 0) = |a|$, $\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$。
应用: 分数化简、扩展欧几里得算法（解线性同余方程）。
示例:
$ \text{gcd}(12, 18) = 6 $
$ \text{gcd}(17, 5) = 1 $ (互质)
C++ 实现 (递归):
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}含义: $\text{lcm}(a, b)$ (Least Common Multiple) 是能同时被 $a$ 和 $b$ 整除的最小正整数。
计算公式: 基于 GCD 计算： $\text{lcm}(a, b) = \frac{|a \times b|}{\text{gcd}(a, b)}$。
注意: 直接计算 $a \times b$ 可能导致溢出，最好写成 $a / \text{gcd}(a, b) \times b$。
应用: 周期问题、任务调度。
示例:
$ \text{lcm}(4, 6) = \frac{4 \times 6}{\text{gcd}(4, 6)} = \frac{24}{2} = 12 $
$ \text{lcm}(5, 7) = \frac{5 \times 7}{\text{gcd}(5, 7)} = \frac{35}{1} = 35 $
C++ 实现:
long long lcm(int a, int b) {
// 需要先包含 gcd 函数
if (a == 0 || b == 0) return 0; // 处理边界
return (long long)a / gcd(a, b) * b; // 防止溢出
}∑ 代数与组合符号
代数符号（如求和、连乘）和组合数学符号（如排列、组合）是分析算法、解决计数问题的基础。
含义: $ \sum_{i=a}^{b} f(i) $ 表示将 $i$ 从 $a$ 到 $b$ (通常是整数步长) 的所有 $f(i)$ 的值加起来。
读法: "西格玛 (Sigma)" 或 "sum from i equals a to b of f(i)"。
常见公式:
- 等差数列: $ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} $
- 等比数列: $ \sum_{i=0}^{n} ar^i = a \frac{r^{n+1}-1}{r-1} $ ($r \neq 1$)
- 平方和: $ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} $
示例:
$ \sum_{i=1}^{4} i^2 = 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30 $
$ \sum_{k=0}^{3} 2^k = 2^0 + 2^1 + 2^2 + 2^3 = 1 + 2 + 4 + 8 = 15 $
含义: $ \prod_{i=a}^{b} f(i) $ 表示将 $i$ 从 $a$ 到 $b$ 的所有 $f(i)$ 的值乘起来。
读法: "派 (Pi)" 或 "product from i equals a to b of f(i)"。
常见应用: 阶乘。
示例:
$ \prod_{i=1}^{n} i = 1 \times 2 \times \dots \times n = n! $ (阶乘)
$ \prod_{k=1}^{3} (k+1) = (1+1) \times (2+1) \times (3+1) = 2 \times 3 \times 4 = 24 $
含义: $n!$ 表示从 1 到 $n$ 的所有正整数的乘积。
定义: $ n! = \prod_{i=1}^{n} i = n \times (n-1) \times \dots \times 1 $。
特殊约定: $0! = 1$。
应用: 排列组合、概率计算。
示例:
$ 4! = 4 \times 3 \times 2 \times 1 = 24 $
$ 1! = 1 $
$ 0! = 1 $
注意: 阶乘增长非常快，计算时需注意溢出。
含义: $ C(n, k) $ 或 $ \binom{n}{k} $ (读作 "n choose k") 表示从 $n$ 个不同的元素中无序地选取 $k$ 个元素的方案数。
计算公式: $ \binom{n}{k} = \frac{n!}{k!(n-k)!} $ (要求 $0 \le k \le n$)
递推公式 (杨辉三角): $ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $
性质: $ \binom{n}{k} = \binom{n}{n-k} $, $ \binom{n}{0} = \binom{n}{n} = 1 $
应用: 二项式定理、路径计数、分配问题。
示例:
$ \binom{4}{2} = \frac{4!}{2!(4-2)!} = \frac{24}{2 \times 2} = 6 $ (从{A,B,C,D}选2个: AB, AC, AD, BC, BD, CD)
$ \binom{5}{3} = \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10 $ (计算技巧)
含义: $ P(n, k) $ 或 $ A_n^k $ 表示从 $n$ 个不同的元素中有序地选取 $k$ 个元素进行排列的方案数。
计算公式: $ P(n, k) = \frac{n!}{(n-k)!} = n \times (n-1) \times \dots \times (n-k+1) $ ($k$ 项)
与组合数关系: $ P(n, k) = \binom{n}{k} \times k! $ (先选后排)
应用: 排序问题、有顺序的安排问题。
示例:
$ P(4, 2) = \frac{4!}{(4-2)!} = \frac{24}{2} = 12 $ (从{A,B,C,D}选2个排列: AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD, DC)
$ P(n, n) = n! $ (全排列)
∧ 逻辑符号与量词
逻辑符号用于表达命题之间的关系，量词则用于限定变量的范围。它们是精确描述算法条件和证明正确性的基础。
含义: $ p \land q $ (读作 "p and q")。当且仅当命题 $p$ 和 $q$ **都**为真时，结果为真。
真值表:
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
编程对应: C++/Java 中的 `&&` 运算符。
示例:
命题 "数字 $x$ 大于 0 且小于 5" 可以表示为 $ (x > 0) \land (x < 5) $。
含义: $ p \lor q $ (读作 "p or q")。当命题 $p$ 和 $q$ **至少有一个**为真时，结果为真。
真值表:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
编程对应: C++/Java 中的 `||` 运算符。
示例:
命题 "数字 $n$ 是偶数或是 3 的倍数" 可以表示为 $ (n \bmod 2 = 0) \lor (n \bmod 3 = 0) $。
含义: $ \neg p $ (读作 "not p")。当命题 $p$ 为假时，结果为真；当 $p$ 为真时，结果为假。
真值表:
| p | ¬p |
|---|---|
| T | F |
| F | T |
编程对应: C++/Java 中的 `!` 运算符。
示例:
$ \neg (x = y) $ 等价于 $ x \neq y $。
德摩根定律: $ \neg (p \land q) \Leftrightarrow (\neg p \lor \neg q) $, $ \neg (p \lor q) \Leftrightarrow (\neg p \land \neg q) $
含义: $ p \Rightarrow q $ (读作 "p implies q" 或 "若 p 则 q")。表示如果 $p$ 为真，那么 $q$ **必须**为真。如果 $p$ 为假，则整个蕴含式为真（无论 $q$ 真假）。
等价形式: $ \neg p \lor q $。
真值表:
| p | q | p ⇒ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
注意: $p$ 是 $q$ 的充分条件，$q$ 是 $p$ 的必要条件。
示例:
命题 "如果一个数是素数且大于2，则它一定是奇数"： $ (p \text{ is prime} \land p > 2) \Rightarrow (p \text{ is odd}) $。
含义: $ p \Leftrightarrow q $ (读作 "p if and only if q"，常缩写为 "iff")。表示 $p$ 和 $q$ 的真值**完全相同**。
等价形式: $ (p \Rightarrow q) \land (q \Rightarrow p) $。
真值表:
| p | q | p ⇔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
应用: 定义、充要条件。
示例:
命题 "一个整数 $n$ 是偶数当且仅当 $n^2$ 是偶数"： $ (n \text{ is even}) \Leftrightarrow (n^2 \text{ is even}) $。
含义: $ \forall x \in S, P(x) $ 表示对于集合 $S$ 中的**所有**元素 $x$，命题 $P(x)$ 都为真。
读法: "对于所有的 x 属于 S，P(x) 成立"。
证伪: 找到一个 $x \in S$ 使得 $P(x)$ 为假即可。
示例:
$ \forall n \in \mathbb{N}, n \ge 0 $ (所有自然数都大于等于0，假设 N={0, 1, ...})
$ \forall x \in \mathbb{R}, x^2 \ge 0 $ (所有实数的平方都非负)
含义: $ \exists x \in S, P(x) $ 表示在集合 $S$ 中**至少存在一个**元素 $x$，使得命题 $P(x)$ 为真。
读法: "存在 x 属于 S，使得 P(x) 成立"。
证明: 找到一个满足条件的 $x$ 即可。
与 $ \forall $ 的关系 (否定): $ \neg (\forall x, P(x)) \Leftrightarrow (\exists x, \neg P(x)) $； $ \neg (\exists x, P(x)) \Leftrightarrow (\forall x, \neg P(x)) $。
示例:
$ \exists n \in \mathbb{Z}, n^2 = 9 $ (存在整数 n=3 或 n=-3，其平方为9)
$ \exists p \in \text{Primes}, p \text{ is even} $ (存在一个偶素数 p=2)
O 复杂度符号 (渐进表示法)
渐进符号用于描述算法在输入规模 $n$ 趋向于无穷大时的运行时间或空间消耗的增长率趋势，是衡量算法效率的核心工具。
含义: $ T(n) = O(f(n)) $ 表示算法的运行时间 $T(n)$ 的增长率**不超过** $f(n)$ 的常数倍 (当 $n$ 足够大时)。它给出了算法效率的**上界**。
形式化定义: 存在正常数 $c$ 和 $n_0$，使得对所有 $ n \ge n_0 $，都有 $ 0 \le T(n) \le c \cdot f(n) $。
常见复杂度 (快到慢): $O(1)$ (常数), $O(\log n)$ (对数), $O(n)$ (线性), $O(n \log n)$ (线性对数), $O(n^2)$ (平方), $O(n^3)$ (立方), $O(2^n)$ (指数), $O(n!)$ (阶乘)。
关注点: 最坏情况下的性能上限。
示例:
二分查找: $ O(\log n) $
归并排序、快速排序 (平均): $ O(n \log n) $
简单的双重循环遍历 $n \times n$ 矩阵: $ O(n^2) $
$ 3n^2 + 5n + 10 = O(n^2) $ (忽略低阶项和常数系数)
含义: $ T(n) = \Omega(f(n)) $ 表示算法的运行时间 $T(n)$ 的增长率**不低于** $f(n)$ 的常数倍 (当 $n$ 足够大时)。它给出了算法效率的**下界**。
形式化定义: 存在正常数 $c$ 和 $n_0$，使得对所有 $ n \ge n_0 $，都有 $ T(n) \ge c \cdot f(n) \ge 0 $。
关注点: 最好情况或任何情况下性能的保证下限。
示例:
任何需要读取 $n$ 个输入的算法至少是 $ \Omega(n) $。
基于比较的排序算法 (如归并、快排、堆排) 的最坏情况和平均情况都是 $ \Omega(n \log n) $。
$ 3n^2 + 5n + 10 = \Omega(n^2) $
含义: $ T(n) = \Theta(f(n)) $ 表示算法的运行时间 $T(n)$ 的增长率与 $f(n)$ **相同** (当 $n$ 足够大时)。它给出了算法效率的**紧确界**。
等价条件: $ T(n) = O(f(n)) $ 且 $ T(n) = \Omega(f(n)) $。
形式化定义: 存在正常数 $c_1, c_2$ 和 $n_0$，使得对所有 $ n \ge n_0 $，都有 $ 0 \le c_1 \cdot f(n) \le T(n) \le c_2 \cdot f(n) $。
关注点: 对算法性能增长率的精确描述。
示例:
归并排序的运行时间总是 $ \Theta(n \log n) $ (无论最好最坏情况)。
查找无序数组中的最大值: $ \Theta(n) $。
$ 3n^2 + 5n + 10 = \Theta(n^2) $。
注意: 快速排序的最坏情况是 $O(n^2)$，平均情况是 $\Theta(n \log n)$，所以不能说快排是 $\Theta(n \log n)$，除非特指平均情况。
含义: $ T(n) = o(f(n)) $ 表示 $T(n)$ 的增长率**严格小于** $f(n)$ 的增长率。意味着 $ \lim_{n \to \infty} \frac{T(n)}{f(n)} = 0 $。
与 Big O 区别: Big O 允许增长率相等 ($ T(n) = O(n^2) $ 且 $ T(n) = O(n^3) $)，而 Little o 要求严格小于 ($ T(n) = o(n^3) $ 但 $ T(n) \neq o(n^2) $ 如果 $ T(n) = \Theta(n^2) $)。
示例:
$ n \log n = o(n^2) $
$ n^2 = o(n^3) $
$ 5n = o(n^2) $
含义: $ T(n) = \omega(f(n)) $ 表示 $T(n)$ 的增长率**严格大于** $f(n)$ 的增长率。意味着 $ \lim_{n \to \infty} \frac{T(n)}{f(n)} = \infty $。
与 Big Omega 区别: 类似于 Little o 和 Big O 的关系。
示例:
$ n^2 = \omega(n \log n) $
$ n^3 = \omega(n^2) $
$ n^2 = \omega(5n) $
常见复杂度的增长速度排序 (从快到慢):
$ O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < \dots < O(2^n) < O(n!) < O(n^n) $
在信息学竞赛中，通常要求算法复杂度在 $O(n)$, $O(n \log n)$, $O(n\sqrt{n})$, $O(n^2)$ 甚至更低才能在规定时间内通过大数据量的测试点（例如 $n \approx 10^5$ 或 $10^6$ 时，$O(n^2)$ 通常会超时）。
⌊⌋ 其他常用符号
除了前面分类介绍的符号外，还有一些零散但同样重要的符号在信息学中经常出现。
含义: $ \lfloor x \rfloor $ (读作 "floor of x") 表示不大于 $x$ 的最大整数。
编程对应: C++/Java 中的 `floor(x)` 函数 (通常返回 double，需转 int)，或直接进行整数除法 (对于正数)。例如 `a / b` (当 a, b 为正整数)。对于负数需注意，如 C++ `-7 / 3` 结果是 `-2`，而 $ \lfloor -7/3 \rfloor = \lfloor -2.33\dots \rfloor = -3 $。
公式: $ \lfloor x \rfloor \le x < \lfloor x \rfloor + 1 $
示例:
$ \lfloor 3.14 \rfloor = 3 $
$ \lfloor 5 \rfloor = 5 $
$ \lfloor -2.7 \rfloor = -3 $
$ \lfloor -4 \rfloor = -4 $
应用: 计算数组索引、分块算法、数论问题。
C++ 安全向下取整: `int floor_div(int a, int b) { int res = a / b; return res * b > a ? res - 1 : res; }` (对 b<0 情况未处理)
或者更简洁地处理负数: `floor(a / (double)b)` 再转int，或者 `(a - (a % b + b) % b) / b` 如果需要纯整数运算。
含义: $ \lceil x \rceil $ (读作 "ceiling of x") 表示不小于 $x$ 的最小整数。
编程对应: C++/Java 中的 `ceil(x)` 函数 (返回 double)。整数运算中常用技巧: `(a + b - 1) / b` (当 a, b 为正整数时，计算 $a/b$ 的向上取整)。
公式: $ \lceil x \rceil - 1 < x \le \lceil x \rceil $
示例:
$ \lceil 3.14 \rceil = 4 $
$ \lceil 5 \rceil = 5 $
$ \lceil -2.7 \rceil = -2 $
$ \lceil -4 \rceil = -4 $
应用: 分配资源（如至少需要多少容器）、计算循环次数。
C++ 整数向上取整: `(a + b - 1) / b` (假设 a >= 0, b > 0)
处理负数: `(a > 0) ? (a + b - 1) / b : a / b` (对 b<0 未处理)
或者通用: `(a % b == 0) ? a / b : a / b + (a * b < 0 ? 0 : 1)` (复杂)
含义: $ \infty $ 表示一个理论上无限大的值或概念，不是一个具体的数字。
用法:
- 极限: $ \lim_{n \to \infty} \frac{1}{n} = 0 $
- 区间表示: $ [a, \infty) $ 表示所有大于等于 $a$ 的实数。
- 算法中表示极大值: 在需要初始化一个极大值（如求最小值问题）时，通常用一个足够大的数 `0x3f3f3f3f` (约 $10^9$) 或 `LLONG_MAX` (约 $9 \times 10^{18}$) 来模拟正无穷。避免使用 `INT_MAX` 直接相加导致溢出。
示例:
Dijkstra 算法初始化距离数组 `dist[i] = infinity`。
求最小值时，`min_val = infinity;` 然后 `min_val = min(min_val, current_val);`
C++ 常用 "无穷大" 值:
const int INF = 0x3f3f3f3f; // ~10^9, int范围, 相加不易溢出
const long long LINF = 0x3f3f3f3f3f3f3f3fLL; // ~9*10^18, long long范围
// #include
// int max_int = std::numeric_limits::max(); // 约 2*10^9
// long long max_ll = std::numeric_limits::max(); // 约 9*10^18 含义: 表示两个数值在一定精度下非常接近。
用法:
- 估算: $ \pi \approx 3.14 $
- 浮点数比较: 在编程中比较两个浮点数 `a` 和 `b` 是否相等时，不能直接用 `a == b`，而应判断它们的差的绝对值是否小于一个很小的正数 $\epsilon$ (epsilon)。 $ |a - b| < \epsilon $
示例:
$ \sqrt{2} \approx 1.414 $
C++ 浮点数比较:
const double EPS = 1e-8; // 定义精度
double a = 0.1 + 0.2;
double b = 0.3;
if (fabs(a - b) < EPS) {
// 认为 a 和 b 相等
std::cout << "a is approximately equal to b" << std::endl;
} else {
std::cout << "a is not equal to b" << std::endl; // 可能输出这个!
}📝 模拟练习
通过下面的练习来检验你对这些数学符号的掌握程度吧！