在简单的语言大-θ和大O符号的区别 [英] Difference between Big-Theta and Big O notation in simple language

问题描述

在试图理解之间的差异西塔和 0 符号，我碰到下面的语句：

While trying to understand the difference between Theta and O notation I came across the following statement :

The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.

但我不明白这一点。这本书解释了它在数学，但它太复杂，变得非常无聊阅读时，我真的不理解。

But I do not understand this. The book explains it mathematically, but it's too complex and gets really boring to read when I am really not understanding.

谁能解释使用的简单但功能强大的例子的两者之间的区别。

Can anyone explain the difference between the two using simple, yet powerful examples.

推荐答案

大O是给只上渐近界，而大西塔也给人一种下限。

Big O is giving only upper asymptotic bound, while big Theta is also giving a lower bound.

一切，这是的Theta（F（N））也是 0（F（N）），但而不是其他方式。
T（N）据说是的Theta（F（N）），如果是两个 0（F（N）） 和 欧米茄（F（N））

Everything that is Theta(f(n)) is also O(f(n)), but not the other way around.
T(n) is said to be Theta(f(n)), if it is both O(f(n)) and Omega(f(n))

由于这个原因大西塔是提供更多的信息，然后大O 记法，所以如果我们能说些什么是大西塔，它通常是preferred。然而，这是很难证明什么大西塔，而不是证明它是大O。

For this reason big-Theta is more informative then big-O notation, so if we can say something is big-Theta, it's usually preferred. However, it is harder to prove something is big Theta, than to prove it is big-O.

有关示例 排序合并既是 O（N *的log（n））和的Theta（N *的log（n）），但它也为O（n < SUP> 2 ），由于n ² 是渐进比做大。但是，它不是西塔（N ² ），因为算法不欧米茄（N ² ）。

For example, merge sort is both O(n*log(n)) and Theta(n*log(n)), but it is also O(n²), since n² is asymptotically "bigger" than it. However, it is NOT Theta(n²), Since the algorithm is NOT Omega(n²).

欧米茄（N）是渐近下界的。如果 T（N）是欧米茄（F（N）），这意味着从一定 N0 ，有一个恒定的 C1 ，使得 T（N）＆GT; = C1 * F（N） 。而大O说，有一个恒定的 C2 ，使得 T（n）的＆LT; = C2 * F（N））。

Omega(n) is asymptotic lower bound. If T(n) is Omega(f(n)), it means that from a certain n0, there is a constant C1 such that T(n) >= C1 * f(n). Whereas big-O says there is a constant C2 such that T(n) <= C2 * f(n)).

这三个（欧米茄，O，西塔）只给出的渐近信息的（对于大输入）：

All three (Omega, O, Theta) give only asymptotic information ("for large input"):

• 在大O给出上限
• 在大欧米茄给出下限和
• 在大西塔同时给出下限和上限

请注意，这个标记是不可以相关算法最佳，最差和平均情况分析。这些的每一个可以被施加到每个分析

Note that this notation is not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.

这篇关于在简单的语言大-θ和大O符号的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！