asymptotic-complexity - 大きなシータ値の比較

Question

これらの異なる大きなシータ値を最大から最小に並べ替えようとしています:

Θ(n2)
Θ(2n log n)
Θ(n log n2)
Θ(2n2)
Θ(log n)
Θ(n log 2n)
Θ(k2)
Θ(22n)
Θ(n3)
Θ(n)
Θ(2n)
Θ(n1.5)
Θ(√n)
Θ(2n2)

一部の値は同等です。特に、定数項が 1 つのビッグ シータ値を定数項のない同一のビッグ シータ項よりも大きくするかどうかを知りたい (たとえば、これら 2 つの値は等しいか: Θ(22n) & Θ(n)?)。

Answer 1

Θ(ログ n)

Θ(√n) = Θ(n ^1/2 )

Θ(n) = Θ(2n) = Θ(22n)

Θ(n log n) = Θ(2n log n) = Θ(n log n ² ) = Θ(n log 2n)

Θ(n ^1.5 )

Θ(n ² ) = Θ(2n ² )

Θ(n ³ )

---

あなたのコメントを考慮して：

n ログ 2n = n (ログ 2 + ログ n) = n ログ 2 + n ログ n

log 2ゼロ以外の定数であるため、次のようになります。

Θ(n log 2n) = Θ(n log 2 + n log n) = Θ(n + n log n) = Θ(n log n)

big-{O,Theta, Omega}表記の定数プロパティによる合計と乗算を参照してください。

Answer 2

n を巨大な値に置き換えてみると、フォーラムに質問しなくても自分で解決できます。

o(1)
O(log log n)
O(log n)
O(n^c)
O(n)
O(n log n)
O(n^2)
O(c^n)
O(n!)