大Omega记号

概述

大Omega记号 给出函数的渐近下界，与 大O记号 对称，描述算法至少需要多少资源。

定义

大Omega记号

$\Omega (g(n))=\{f(n):\exists c>0,\exists n_0>0,\text{使得 }0\le c\cdot g(n)\le f(n),\forall n\ge n_0\}$ 读作 ”$f(n)$ 是 $g(n)$ 的大Omega”。

核心性质

• $\Omega (g(n))$ 是一个函数集合，$f(n)=\Omega (g(n))$ 表示 $f(n)$ 的增长至少和 $g(n)$ 一样快。
• $\Omega$ 给出的是下界，不一定是紧界：$n^2=\Omega (n)$ 成立，但 $n$ 不是 $n^2$ 的紧下界。
• 与 $O$ 记号的对偶关系：$f(n)=\Omega (g(n))$ 当且仅当 $g(n)=O(f(n))$。
• 极限判别：若 ${\lim }_{n\to \infty }f(n)/g(n)>0$（含 $=\infty$），则 $f(n)=\Omega (g(n))$。

章节扩展

第3章：运行时间刻画

• 3.1 O记号、Ω记号与Θ记号 给出 $\Omega$ 记号的形式化定义，并与 $O$ 记号对比讨论。

参见

• 渐近记号
• 大O记号
• 大Theta记号