big-o - 指数関数的および対数的複雑さの Big O 表記法

Question

ビッグオー記法については多くの質問がありますが、この質問に対する明確な答えは見つかりませんでした。

次のように書きます:
O(5n) = O(n)
および
O(3n^2 + n + 2) = O(n^2)

O(2^(2n)) = O(2^n)と書けるでしょうか?

対数の複雑さについても同じ: O(n log(4n)) = O(n log(n))?

Answer 1

削除できる定数は、加法的および乗法的の定数のみです。意味 O(f( n )) = O(f( n ) + C) = O(C × f( n ))。

2 ^{2 n} = (2 ⁿ ) ²。この 2 定数は指数であるため無視できません。O( n ) と O( n ² ) が異なる複雑度クラスであるように、O(2 ⁿ ) と O(2 ^{2 n} ) も異なります。

一方、はい、O( n log 4 n ) = O( n log n ) です。対数恒等式を使用して、4 を乗法定数に変換できます。 O( n log 4 n ) = O( n (log n + log 4)) = O( n log n + (log 4) n ) = O( n log n + n ) = O( n log n )。