complexity-theory - 复杂性 - 大 O 表示法，theta 和 omega

Question

谁能帮我验证以下复杂性：

    10^12 = O(1)?
    2^(n+3) + log(n) = O(2^n)?
    f(n) = Omega(n) and f(n) = theta(n) <=> f(n) = O(n)

谢谢

Answer 1

前两个是对的，最后一个是错的。

特别是，任何没有附加变量的值都是“常数”，因此 O(1)。至于为什么你在第二个是正确的，2^n 严格渐近地击败 log(n)，并且 2^(n+3) 相当于 8*2^n，或者 O(1)*O(2^n )，通常最好将大 O 表示法简化为最简单的正确形式。

第三个条件是错误的，因为 f(n) = O(n) 并不暗示前两个语句中的任何一个。