O(1)和Θ(1)有何区别？

Question

我知道它们的定义，但为什么有时候在教科书中看到O(1)，而其他时候看到Θ(1)呢？

谢谢。

- Barak Aburus

---

我经常在CLRS的文本中看到作者使用O(1)来表示一个常量语句，而不是Theta(1)。虽然这本书非常具体。使用大O表示需要恒定时间执行的语句的原因之一是，人们更关心最坏情况，这反映在大O符号上...但是，如果条件执行语句，则需要恒定时间执行的语句确实可以为总执行时间贡献O(1)，而不是Theta(1)。因此，它没有执行的保证，因此其成本不受1的下限约束。 - Abhishek Ghosh

Answer 1

如果你谈论实数函数，那么O（1）和Θ（1）不一定相同。例如，考虑函数f（n）= 1 / n。对于任何n≥1，此函数都是O（1），因为f（n）≤1。但是，它并非Θ（1），原因如下：f（n）= Θ（g（n））的一个定义是当n无限增大时，|f（n）/ g（n）|的极限是一些满足0＜L的有限值L。将f（n）= 1 / n和g（n）= 1代入此定义，我们取|1 / n|随着n趋向无穷大的极限，结果为0。因此，f（n）≠Θ（1）。希望这能帮到你！

- templatetypedef

Answer 2

大O符号表示渐进上界，而大Theta符号还表示渐进下界。通常，人们感兴趣的是上界，因此即使Theta（something）也成立，他们仍会写O（something）。例如，如果您想计算未排序列表中等于x的元素数量，您可能会说它可以在线性时间内完成，并且是O（n），因为对您来说重要的是它不会花费更长的时间。但是，它也是Omega（n），因此是Theta（n），因为您必须检查列表中的所有元素-它不能在次线性时间内完成。

更新：

正式地说：

• 如果存在c和n0，使得对于所有n > n0，f(n) <= c * g(n)，则f在O(g)中。

• 如果存在c和n0，使得对于所有n > n0，f(n) >= c * g(n)，则f在Omega(g)中。

• 如果f在O(g)中且f在Omega(g)中，即存在c1、c2和n0，使得对于所有n > n0，c1 * g(n) <= f(n) <= c2 * g(n)，则f在Theta(g)中。

- Stuart Golodetz

---

谈到常量时，它们之间有区别吗？ 还有一种情况是需要Theta 1而不是O 1吗？ - Barak Aburus

在谈论常数时间时没有区别，因为下限是暗示的。但是请参阅此处的有趣讨论：https://dev59.com/rnNA5IYBdhLWcg3wk-6A - Stuart Golodetz

你确定吗？我认为我的答案中有反例。 - templatetypedef

这个答案是不正确的，不应该被标记为正确答案。它正在传播错误信息。Big-Theta代表大n（ish）的平均时间，与下限无关。下限由Big-Omega定义。 - mazunki

我之前阅读时完全忽略了“另外”这部分。我撤回之前的说法，因为Θ(f)确实代表一个夹逼，而不仅仅是一个上取整或下取整。 - mazunki