算法复杂度的渐进符号定义,证明与理解

Fri, 13 Feb 2026 00:00:00 +0000

算法复杂度的渐进符号定义与理解

$T(N) = O(f(N))$ if there are positive constants $c$ and $n_0$ such that $T(N) \leq c \cdot f(N)$ when $N \geq n_0$.

$T(N) = \Omega(g(N))$ if there are positive constants $c$ and $n_0$ such that $T(N) \geq c \cdot g(N)$ when $N \geq n_0$.

$T(N) = \Theta(h(N))$ if and only if $T(N) = O(h(N))$ and $T(N) = \Omega(h(N))$.

Wed, 28 Jan 2026 00:00:00 +0000

理解模块是笔者个人心得体会，如果有误欢迎留言指出

设 $V$ 是域 $\mathbb{K}$ 上的 $n$ 维向量空间，$A$ 是一个非空集合，$A$ 中的元素称为点(point)。如果存在满足以下条件的加法映射 $$+: A \times V \to A, \quad(p, x) \mapsto p + x \in A$$