渐近表示法

渐近表示法

渐近表示法用于表示算法复杂度以进行渐近分析。这些表示法是用于表示复杂度的数学工具。通常使用三种表示法。

大 O 表示法

大 O（O）表示法为函数 f(n) 提供了一个上界，精确到常数因子。

如果存在正数常数 n0 和 c，使得在 n0 的右侧 f(n) 始终位于 c*g(n) 上方或下方，我们写 f(n) = O(g(n))。

O(g(n)) = { f(n) : 存在正数常数 c 和 n0，使得对于所有 n ≥ n0，0 ≤ f(n) ≤ c g(n)}

大 Ω 表示法

大 Ω（Ω）表示法为函数 f(n) 提供了一个下界，精确到常数因子。

如果存在正数常数 n0 和 c，使得在 n0 的右侧 f(n) 始终位于 c*g(n) 上方或下方，我们写 f(n) = Ω(g(n))。

Ω(g(n)) = { f(n) : 存在正数常数 c 和 n0，使得对于所有 n ≥ n0，0 ≤ c g(n) ≤ f(n)}

大 Θ 表示法

大 O（Θ）符号用于在常量范围给出一个函数 f(n) 的界。

如果存在正整数 n0 以及常数 c1 和 c2，使得 n0 右边的 f(n) 始终在 c1*g(n) 和 c2*g(m) 之间（含边界），则我们写 f(n) = Θ(g(n))。

Θ(g(n)) = {f(n) : 存在正整数 c1、c2 和 n0，使得对于所有 n ≥ n0，均有 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)}

Samual Sam

更新于： 2023 年 10 月 21 日

已查看 29K+ 次

开启你的 职业

完成课程即可获得认证

开始