この指数アルゴリズムのBig-O複雑さの単純化

Question

私は一般的なbig-o記述を得るための計算アルゴリズムを持っています。ひどく入れ子になってひどく指数関数的です。ここでは、次のとおりです。ここで

1. For each T_i in T 
2. For k = 1 to max_k 
3. For each of 2^k*(n choose k) items 
4. For each t in T_i 
5. check if the item is in t...etc. 

は、実行中の各時間

1. これは、単純な分割であると私はちょうどそれを定数C1を与えるつもりのライン・バイ・ラインアイデアです。
2. max_kは小さい数で、常にnより小さく、おそらく4または5前後です。私は以下のkを使用します。
3. このループは常に2^k *（nはk回）実行されます
4. 行1を定数と考えると、この行を一般化することができ、最悪の場合合計2^n回以上発火することはありませんが（2^n）/ c2と呼ぶ
5. これは、これらのすべてのループの中の単純なif文の操作であり、したがってc3です。乗算

これらすべて一緒に提供します：

c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3 

私はビッグOの表現をしたいので、定数を無視しています：

k * 2^k * (n choose k) * (2^n) 

（nはk個を選ぶ）が有界であることが知られています（n * e/k）^ kであるので、

O(k * 2^k * (n * e/k)^k * (2^n)) 

私のクエストここで無視できるものは何か... 2^nは確かにnが常にkより大きく、典型的にはそれよりも大きいので、支配的な項です。これをO（2^n）に単純化できますか？またはO（2 ^ひどい）？または、私はO（2^k * 2^n）のように2^kの中に残すべきですか？ （またはすべての条件を残しておいてください）

私が理解していることは、kまたはmax_kがnと競合したり超越することができれば、それらが重要であるということです。しかし、それらは常に支配的なので、多項式実行時間のより低い次数の項のように破棄することはできますか？私はすべての指数関数的な実行時間の混乱が私を混乱させると思います。アドバイスをいただければ幸いです。意味 - -

Answer 1

私の理解では、Kまたはmax_kがnを競うまたは上回ることができれば、その後、 は、彼らが

真不可欠ですが、周りに他の方法がないということである、それが無視できないときにそれをたとえそれがnと競合しなくても、大きなO表記になる。 max_kが定数（定数cのようなものがk <= c）に限定されている場合に限り無視されます。例えば、O(n * logk)アルゴリズムは、k因子が限定されていないのでO(n)ではないので、cのすべてに対してnlogk > c*nとなるようにkが存在します。

あなたが得た表現は製品なので、無視できるものはすべてあなたの場合はeO(k*2^k * (n/k)^k * 2^n)です。

kが有界であれば、あなたは表現としてもでランダウの記号から削除することができ、あなたがO(n^k* 2^n)を取得します。この場合でも、n^k << 2^nですが、すべての定数cにはc*2^n < n^k *2^nのようなnが存在するため、アルゴリズムはO(2^n)ではないため、無視することはできません。

追加にあたっては、より小さな要素は無視することができます。製品を扱うときc*n < n + kが、これはもちろん真実ではありません。その後、k < nO(n + k) = O(n)場合は、理由n > Nすべてのためになるように定数c,Nあります。