O(1)和Θ(1)之间有什么区别？

Question

我知道它们两者的定义,但有时我看到O(1)和其他时间Θ(1)写在教科书中的原因是什么？

谢谢.

Answer 1

如果你在谈论实数上的函数,O(1)和Θ(1)不一定相同.例如,考虑函数f(n)= 1/n.该函数为O(1),因为对于任何n≥1,f(n)≤1.但是,由于以下原因,它不是 Θ(1):f(n)的一个定义=Θ(g(n))是| f(n)/ g(n)|的极限 当n变为无穷大时,一些有限值L满足0 <L.在f(n)= 1/n和g(n)= 1的插入中,我们取| 1/n |的极限.当n变为无穷大并得到它为0.因此,f(n)≠Θ(1).

希望这可以帮助!

Answer 2

Big-O 表示法表示渐近上限，而 Big-Theta 表示法还表示渐近下界。通常，上限是人们感兴趣的，因此他们写 O(something)，即使 Theta(something) 也为真。例如，如果您想计算未排序列表中等于 x 的数量，您可能会说它可以在线性时间内完成并且是 O(n)，因为对您来说重要的是它不会'不需要比这更长的时间了。然而，它也可能是 Omega(n)，因此也是 Theta(n)，因为您必须检查列表中的所有元素 - 它不能在亚线性时间内完成。

更新：

正式：

• f 在 O(g) 中当且仅当存在 ac 和 n0 使得对于所有 n > n0，f(n) <= c * g(n)。

• f 在 Omega(g) 中当且仅当存在 ac 和 n0 使得对于所有 n > n0，f(n) >= c * g(n)。

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