complexity-theory - 複雑さ - 大きな O 記法、シータとオメガ

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

最初の 2 つは正しく、最後の 2 つは誤りです。

特に、変数が付加されていない値は「定数」であり、したがって O(1) になります。2番目に正しい理由については、2^nは厳密にlog(n)を漸近的に打ち負かし、2^(n+3)は8*2^nまたはO(1)*O(2^n)と同等です)、一般的には、big-O 表記を最も単純に見える正しい形式に簡略化するのが最善です。

f(n) = O(n) は最初の 2 つのステートメントのいずれも意味しないため、3 番目の条件は正しくありません。