I know the definitions of both of them, but what is the reason sometimes I see O(1) and other times Θ(1) written in textbooks?
Thanks.
问问题
10405 次
2 回答
9
如果您谈论的是实数上的函数，O(1) 和 Θ(1) 不一定相同。例如，考虑函数 f(n) = 1/n。这个函数是 O(1)，因为对于任何 n ≥ 1，f(n) ≤ 1。但是，它不是Θ(1)，原因如下：f(n) = Θ(g(n)) 的一个定义是|f(n) / g(n)| 的极限吗？当 n 趋于无穷时，是某个满足 0 < L 的有限值 L。代入 f(n) = 1/n 和 g(n) = 1，我们取 |1/n| 的极限 当 n 趋于无穷大时，它为 0。因此，f(n) ≠ Θ(1)。
希望这可以帮助！
于 2013-09-15T23:05:59.063 回答
0
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)。
Omega(g) 中的 f 当且仅当存在 ac 和 n0 使得对于所有 n > n0，f(n) >= c * g(n)。
f 在 Theta(g) 中当且当 f 在 O(g) 和 f 在 Omega(g) 中，即当且仅当存在一个 c1、一个 c2 和一个 n0 使得对于所有 n > n0，c1 * g(n) <= f (n) <= c2 * g(n)。
于 2013-09-07T20:28:18.713 回答