简单说一下Big-Theta和Big O符号的区别

Question

简单说一下Big-Theta和Big O符号的区别

51

在试图理解 Theta 和 O 符号之间的区别时，我遇到了以下声明：

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

但我不理解这个。书里用数学方式解释，但过于复杂，当我真的无法理解时阅读起来非常枯燥。

有人能用简单而又有效的例子来解释两者之间的区别吗？

- Suhail Gupta

@Ash Burlaczenko，正如我所提到的，我觉得这很无聊，因为我不理解。我想这是显而易见的！ - Suhail Gupta

2

@Suhail，你的符号在我的浏览器中没有显示。已编辑。 - UmNyobe

另一个例子是插入排序和选择排序。它们在最坏情况下都是O(n^2)，但在最好情况下，插入排序的执行时间为O(n)，而选择排序对所有情况都是O(n^2)。我们将说插入排序是O(n^2)，而选择排序是Theta(n^2)（下限=上限）。 - nhahtdh

2

@nhahtdh：您的示例是具有误导性的。最好情况和最差情况与大O/Theta符号无关。这些（大O/Theta）属于包括函数在内的数学集合。如果最坏情况和最好情况相同，我们不会说一个算法是Theta(f(n))，相反，我们会说它在最坏情况下是Theta(f(n))（例如），如果最坏情况既是O(f(n))又是Omega(f(n))，而不管最好情况的行为如何。 - amit

1

@nhahtdh：这是错误的。插入排序的最坏情况是Theta(n^2)，因为你可以在最坏情况下的输入（反向排序数组）上给出需要多少操作的下限，并且它将与元素数量的平方成比例。在没有指明分析方式的情况下谈论算法的复杂度是没有意义的。通常情况下，如果省略了分析，那么它隐含地意味着复杂度是在最坏情况分析下计算的。如果我们使用这个约定，插入排序是Theta(n^2) [最坏情况分析隐含在这个说法中]。 - amit

显示剩余2条评论

5个回答

11

我将直接引用 Knuth 的《计算机程序设计艺术》第一卷 - 第110页（我有印度版）。我建议阅读107-110页（1.2.11 节“渐近表示”）。

人们经常会混淆 O表示法，认为它给出了精确的增长顺序；他们使用它时好像它同时指定了下限和上限。例如，一个算法可能因其运行时间为O(n^2)而被称为低效率。但是，O(n^2)的运行时间并不一定意味着运行时间不是O(n)

在第107页中，

1^2 + 2^2 + 3^2 + ... + n^2 = O(n^4) 和

1^2 + 2^2 + 3^2 + ... + n^2 = O(n^3) 和

1^2 + 2^2 + 3^2 + ... + n^2 = (1/3) n^3 + O(n^2)

大 O 表示法用于估算。它可以让您使用 ~ 替换等号 = 符号。在上面的例子中，对于非常大的n，我们可以确定该数量将保持在 n^4、n^3 和 (1/3)n^3 + n^2 [而不仅仅是 n^2] 以下。

大 Omega 表示法用于下限 - 一个具有Omega(n^2)的算法对于大N来说不会像O(N logN)一样高效。但是，我们不知道在哪些N值处（在这个意义上，我们只知道近似值）。

大 Theta 表示法用于精确的增长顺序，既有下限也有上限。

- rjha94

5

这里是我的翻译：

一个函数 f(n) 是 O(n)，当且仅当存在一个常数 c，使得 f(n) <= c*g(n)。按照这个定义，我们可以说函数 f(2^(n+1)) 是 O(2^n) 吗？

1. 换句话说，是否存在一个常数 'c'，使得 2^(n+1) <= c*(2^n)？注意，上述问题中的大O后面的函数（2^n）是第二个函数。这最初让我感到困惑。 2. 然后使用基本的代数技能简化方程：2^(n+1) 可以拆分为 2 * 2^n。于是，我们得到了：2 * 2^n <= c(2^n)。 3. 现在很容易看出，对于任何 c 值都满足该方程，其中 c >= 2。因此，我们可以说 f(2^(n+1)) 是 O(2^n)。

大 Omega 的工作方式相同，只不过它评估 f(n) >= c*g(n)，其中 'c' 是某个常数。

因此，以同样的方式简化上述函数，我们得到以下式子（注意现在是 >=）：2 * 2^n >= c(2^n)。

因此，此方程适用于范围 0 <= c <= 2。因此，我们可以说 f(2^(n+1)) 是 (2^n) 的大 Omega。

现在，由于上述两个结论都成立，我们可以说该函数是大 Theta（2^n）。如果其中一个不适用于常数 'c'，则它就不是大 Theta。

上述示例摘自 Skiena 的《算法设计手册》，这是一本非常好的书。

希望这有所帮助。这确实是一个难以简化的概念。不要过分关注 'c' 是什么，只需要将其拆解为更简单的术语并使用基本的代数技能即可。

- sma

5

如果运行时间用大O符号表示，你会知道运行时间不会慢于给定的表达式。它表示最坏情况。

但是，使用Theta符号，您也知道它不会更快。也就是说，没有最好情况下算法返回速度更快。

这为预期运行时间提供了更精确的界限。但是，对于大多数目的来说，忽略下限（更快执行的可能性）会更简单，因为你通常只关心最坏情况。

- faester

5

我将用一个例子来说明区别。

让函数f(n)定义为：

if n is odd f(n) = n^3
if n is even f(n) = n^2

来自CLRS

如果存在正常数c1和c2，使得对于足够大的n，函数f(n)可以被"c1g(n)"和"c2g(n)"夹在中间，则函数f(n)属于集合Θ(g(n))。

AND

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

AND

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

f(n)的上界是n^3。因此，我们的函数f(n)显然是O(n^3)。

但它是否是Θ(n^3)？

对于f(n)属于Θ(n^3)，它必须夹在两个函数之间，一个形成下界，另一个形成上界，两个函数都以n^3增长。尽管上界很明显，但下界不能是n^3。事实上，下界是n^2；f(n)为Ω(n^2)。

来自CLRS

对于任意两个函数f(n)和g(n)，当且仅当f(n) = O(g(n)) 且f(n) = Ω(g(n)) 时，我们有f(n) = Θ(g(n))。

因此，f(n)不属于Θ(n^3)，但它属于O(n^3)和Ω(n^2)。

- VSOverFlow

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

大O表示的是渐进上界，而大Theta同时也提供了一个下界。

所有的Theta(f(n))都是O(f(n))，但反过来则不成立。
如果T(n)既是O(f(n))又是Omega(f(n))，那么它被称为Theta(f(n))

因此，大Theta符号比大O符号更具信息量，如果我们可以说某个东西是大Theta，通常会更好。然而，证明某个东西是大Theta比证明它是大O要困难得多。

例如，归并排序既是O(n*log(n))，也是Theta(n*log(n))，但它也是O(n²)，因为n²在渐进意义下“更大”。但是，它不是Theta(n²)，因为该算法不是Omega(n²)。

Omega(n) 是一种渐进下限。如果 T(n) 是 Omega(f(n))，则意味着从某个特定的 n0 开始，存在一个常数 C1，使得 T(n) >= C1 * f(n)。而大O表示存在一个常数 C2，使得 T(n) <= C2 * f(n))。

所有三个符号（Omega、O、Theta）只提供渐进信息（“对于大输入”）：

- 大O提供上限 - 大Omega提供下限 - 大Theta提供上下限

请注意，这些符号与算法的最好、最坏和平均情况分析无关。每种分析都可以应用于这三个符号。