我知道它们的定义,但为什么有时候在教科书中看到O(1),而其他时候看到Θ(1)呢?
谢谢。
谢谢。
大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)中。