[解決済み] 2^nとn*2^nは同じ時間複雑性か？

質問

私が見つけた時間の複雑性に関する資料は、特に多項式でない例で、時間の複雑性の方程式の中の項を無視してもよい場合について不明瞭です。

という形のものがあれば、n ² + n + 1の場合、最後の2項は重要ではありません。

具体的には、2つのカテゴリ分けがある場合、2 ⁿ とn*(2) ⁿ ) の場合、2番目は1番目と同じ順番になるのでしょうか？そこでの追加のn乗は重要ですか？通常、リソースは単にx ⁿ が指数関数になり、より速く成長する...といった具合で、先に進みます。

2なので、そうならないのは理解できます。 ⁿ はnを大きく上回りますが、足し算ではないので、2つの式を比較するときに大きく問題になります。実際、2つの式の差は常にnのファクターになるので、控えめに言っても重要だと思われます。

どのように解くのですか？

ビッグオーの正式な定義に行く必要があります( O この質問に答えるために。

という定義になっています。 f(x) に属しています。 O(g(x)) が制限されている場合のみ limsupx → ∞ (f(x)/g(x)) が存在する、つまり無限大ではありません。要するにこれは、ある定数が存在することを意味する。 M の値が f(x)/g(x) よりも大きくなることはありません。 M .

ご質問の場合、以下のようにします。 f(n) = n ⋅ 2n とし g(n) = 2n . 次に f(n)/g(n) は n は、まだ無限に成長する。したがって f(n) には属さない。 O(g(n)) .