算法分析 | 小 o 和小欧米茄符号

渐近分析的主要思想是衡量算法的效率，而不依赖于机器特定的常数，主要是因为这种分析不需要实现算法和比较程序所花费的时间。我们已经讨论了三种主要的渐近符号。下面两个渐近符号用于表示算法的时间复杂度。

小 ο 渐近符号

Big-Ο 用作算法工作量增长的紧密上限（此工作量由函数 f(n) 描述），尽管如所写，它也可以是松散的上限。“小ο”(ο()) 表示法用于描述不能紧的上限。

定义： 让 f(n) 和 g(n) 是将正整数映射到正实数的函数。如果对于任何实常数 c > 0，存在整数常数 n0 ≥ 1 使得 0 ≤ f(n) < c*g(n)。因此，小的 o() 意味着f(n) 的上界松散。Little o 是对最大增长顺序的粗略估计，而 Big-Ο 可能是实际增长顺序。在数学关系中，f(n) = o(g(n)) 表示lim f(n)/g(n) = 0 n→∞

例子：

7n + 8 ∈ o(n 2 )

为了使之成立，对于任何 c，我们必须能够找到使
f(n) < c * g(n) 渐近正确的 n0 。
让我们举一些例子，
如果 c = 100，我们检查不等式显然是正确的。如果 c = 1/100 ，我们将不得不使用
更多的想象力，但我们将能够找到 n0。（尝试 n0 = 1000。）从
这些例子中，猜想似乎是正确的。
然后检查限制，
lim f(n)/g(n) = lim (7n + 8)/(n 2 ) = lim 7/2n = 0 (l’hospital)
n→∞ n→∞ n→∞

因此 7n + 8 ∈ o(n 2 )

小ω渐进符号

定义： 让 f(n) 和 g(n) 是将正整数映射到正实数的函数。如果对于任何实常数 c > 0，存在整数常数 n0 ≥ 1 使得 f (n) > c * g(n) ≥ 0 对于每个整数 n ≥ n0。

f(n) 比 g(n) 具有更高的增长率，因此 Big Omega (Ω) 和 Little omega (ω) 之间的主要区别在于它们的定义。在 Big Omega f(n)=Ω(g(n) )) 并且界限是 0<=cg(n)<=f(n)，但是在小欧米茄的情况下，对于 0<=c*g(n)<f(n) 是正确的。

Big Omega (Ω) 和 Little Omega (ω) 之间的关系类似于 Big-Ο 和 Little o 之间的关系，只是现在我们正在查看下限。小欧米茄 (ω) 是对增长顺序的粗略估计，而大欧米茄 (Ω) 可能代表确切的增长顺序。我们使用 ω 符号来表示一个不渐近紧的下界。
并且，f(n) ∈ ω(g(n)) 当且仅当 g(n) ∈ ο((f(n))。

在数学关系中，
如果 f(n) ∈ ω(g(n)) 那么,

lim f(n)/g(n) = ∞
n→∞

例子：

证明 4n + 6 ∈ ω(1)；

可以通过应用下面给出的极限公式来证明小的 omega(ο) 运行时间。
如果 lim f(n)/g(n) = ∞ 那么函数 f(n) 是 ω(g(n))
n→∞
这里，我们有函数 f(n)=4n+6 和 g(n)=1
lim (4n+6)/(1) = ∞
n→∞
并且，同样对于任何 c 我们可以得到 n0 对于这个不等式 0 <= cg(n) < f(n), 0 <= c1 < 4n+6
由此证明。