Big-oh vs big-theta

Possible Duplicate:
What is the difference between Θ(n) and O(n)?

It seems to me like when people talk about algorithm complexity informally, they talk about big-oh. But in formal situations, I often see big-theta with the occasional big-oh thrown in. I know mathematically what the difference is between the two, but in English, in what situation would using big-oh when you mean big-theta be incorrect, or vice versa (an example algorithm would be appreciated)?

Bonus: why do people seemingly always use big-oh when talking informally?

145014 次浏览
小开

因为有些算法的最佳情况是快速的，所以从技术上来说，它是一个大 O，而不是一个大 Θ。

大 O 代表 上界大 Θ 代表 等价关系。

小开
最佳答案

大 O 是上界。

大 Θ 是一个紧界，即 还有的上下界。

当人们只担心可能发生的最糟糕的情况时，big-O 就足够了; 也就是说，“不可能比这更糟糕了”。当然，约束越紧越好，但是约束并不总是容易计算的。

参见

相关问题

下面这段来自维基百科的引文也说明了一些问题:

非正式地，特别是在计算机科学中，大 O 符号通常是 permitted to be somewhat abused to describe an asymptotic tight bound 在什么情况下使用大 Θ 符号更合适呢 在特定的情况下。

例如，当考虑函数 T(n) = 73n3+ 22n2+ 58时，以下所有内容通常都是可以接受的，但绑定的紧密性(例如，下面的项目2和项目3)通常比松散的绑定(例如，项目1)更受欢迎 下文)。

  1. T(n) = O(n100), which is identical to T(n) ∈ O(n100)
  2. T(n) = O(n3)，与 T(n) ∈ O(n3)完全相同
  3. T(n) = Θ(n3)，与 T(n) ∈ Θ(n3)完全相同

The equivalent English statements are respectively:

  1. T(n)渐近生长速度不快于 n100
  2. T(n)渐近生长速度不快于 n3
  3. T(n) grows asymptotically as fast as n3.

因此，尽管所有三个语句都为真，但是包含的信息越来越多 然而，在某些字段中，大 O 符号(上面列表中的第2个项目符号) 会比大 Θ 符号更常用 因为增长较慢的函数更受欢迎。

小开

我看过《大西塔》而且我很确定我在学校里学到了区别。不过我还是查了一下。维基百科是这么说的:

大 O 是比较函数最常用的大O符号，尽管在许多情况下，大 o 可能会被渐近更紧的大 Θ 所取代。

资料来源: 大 O 符号 # 相关大O符号

我不知道为什么人们在正式交谈时用 Big-O。也许是因为大多数人对 Big-O 比对 Big-Theta 更熟悉？在你提醒我之前，我都忘了《大西塔》的存在。虽然现在我的记忆被刷新了，但我可能最终会在谈话中使用它。:)

小开

Bonus: why do people seemingly always use big-oh when talking informally?

因为在这个循环里:

for i = 1 to n do
something in O(1) that doesn't change n and i and isn't a jump

是 O(n), O(n^2), O(n^3), O(n^1423424)。Big-oh 只是一个上界，这使得计算更加容易，因为您不必找到一个紧界。

然而，上面的循环是 只有 big-theta(n)。

埃拉托斯特尼筛法的复杂度是多少？如果你说 O(n log n)，你不会错，但这也不是最好的答案。如果你说的是 big-theta(n log n)，那你就错了。

小开

我是一个数学家，我已经看到并且需要大 -O O(n)，大 -Theta Θ(n)，和大 -Omega Ω(n)符号一次又一次，而不仅仅是为了算法的复杂性。正如人们所说，大 Θ 是一个双边界。严格地说，当你想解释一个算法能做到多好时，你应该使用它，要么这个算法不能做得更好，要么没有一个算法能做得更好。例如，如果你说“排序需要 Θ (n (log n))比较最坏情况的输入”，那么你就是在解释有一个排序算法对任何输入使用0(n (log n))比较，对于每个排序算法，有一个输入强迫它进行 Ω (n (log n))比较。

Now, one narrow reason that people use O instead of Ω is to drop disclaimers about worst or average cases. If you say "sorting requires O(n(log n)) comparisons", then the statement still holds true for favorable input. Another narrow reason is that even if one algorithm to do X takes time Θ(f(n)), another algorithm might do better, so you can only say that the complexity of X itself is O(f(n)).

然而，人们非正式地使用 O 还有一个更广泛的原因。从人的角度来看，如果从上下文来看，相反的一面是“显而易见的”，那么总是作出双面陈述就是一种痛苦。因为我是一个数学家，所以我总是很小心地说“只有下雨的时候我才会带伞”或者“我会玩4个球，但不会玩5个”，而不是“下雨的时候我会带伞”或者“我会玩4个球”。但这类声明的另一半往往是明显有意或明显无意的。对显而易见的事情草率处理是人类的天性。吹毛求疵很让人困惑。

不幸的是，在一个严格的领域，如数学或算法理论，这也是混淆不分头。当人们应该说 Ω 或 Θ 的时候，他们不可避免地会说 O。因为“显而易见”而忽略细节总会导致误解。这个问题没有解决办法。

小开

这里有很多好的答案，但我注意到有些东西不见了。大多数答案似乎暗示人们使用大 O 而不是大 Θ 的原因是一个困难的问题，在某些情况下这可能是真的。通常导致大 θ 结果的证明要比导致大 O 结果的证明复杂得多。这通常是正确的，但我不认为这与使用一种分析而非另一种分析有很大关系。

当我们谈论复杂性的时候，我们可以说很多东西。大 O 时间复杂度只是告诉我们一个算法保证在什么范围内运行，一个上限。大欧米茄很少被讨论，它告诉我们一个算法保证运行的最短时间，一个下限。现在大 Θ 告诉我们，对于给定的分析，这两个数字实际上是相同的。这告诉我们应用程序有一个非常严格的运行时间，它只能偏离一个渐近小于我们的复杂性的值。许多算法只是没有上界和下界，恰好是渐近等价的。

So as to your question using Big O in place of Big Theta would technically always be valid, while using Big Theta in place of Big O would only be valid when Big O and Big Omega happened to be equal. For instance insertion sort has a time complexity of Big О at n^2, but its best case scenario puts its Big Omega at n. In this case it would not be correct to say that its time complexity is Big Theta of n or n^2 as they are two different bounds and should be treated as such.

小开

因为我的键盘有一个 O 键。
它没有 Θ 或 Ω 键。

我怀疑大多数人同样懒惰，当他们表示 Θ 时使用 O，因为它更容易输入。

小开

大 O 经常被使用的一个原因是因为它经常被使用。很多人看到符号和 好好想想，他们知道它的意思，然后自己(错误地)使用它。这种情况经常发生在那些接受过正规教育的程序员身上——我自己也曾经有过这样的负罪感。

另一个原因是，在大多数非希腊语键盘上输入一个大写的 O 比输入一个大写的 θ 要容易。

但我觉得很多都是因为某种妄想症。我曾在国防相关编程领域工作过一段时间(当时对算法分析知之甚少)。在这种情况下，最坏的情况表现总是人们感兴趣的，因为最坏的情况可能只是发生在错误的时间。如果发生这种情况的可能性远远小于所有船员在同一时刻突然心脏病发作的可能性，这并不重要——它仍然发生。

当然，很多算法在非常常见的情况下都会遇到最坏的情况——经典的例子是按顺序插入二叉树以获得有效的单链表。对平均业绩的“真实”评估需要考虑到不同类型投入的相对频率。


提交答案