6

一般的な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回の何分の1かで実行されるため、これを（2 ^ n）/ c2
  5. これは、これらすべてのループ内の単純なifステートメント操作であるため、c3です。

これらすべてを掛け合わせると、次のようになります。

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

big-O表現が必要なので、定数を無視すると次のようになります。

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

（n Choose k）は（n * e / k）^ kによって制限されることが知られているので、次のようになります。

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

私の質問は、ここで何を無視できるかということです... nは常にkよりも大きく、通常ははるかに大きいため、2^nは確かに支配的な用語です。これをO（2 ^ n）に簡略化できますか？またはO（2 ^ひどい）？または、O（2 ^ k * 2 ^ n）のように、2 ^ kのままにする必要がありますか？（またはすべての用語を残しますか？）

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

4

1 に答える 1

8

私の理解では、kまたはmax_kがnと競合または超えることができる場合、それらは不可欠です。

本当ですが、その逆はそうではありません-つまり-それがnと競合していなくても、大きなO表記に関しては無視できません。max_kが定数で囲まれている場合にのみ無視できます（のcような定数がありk <= cます）。たとえば、-O(n * logk)アルゴリズムは、ではありません。これは、k係数が制限されておらず、したがって、すべての定数に対してそのようなものO(n)が存在するためです。knlogk > c*nc

取得した式は積であるため、無視できるのは定数だけです。この場合、-はe取得するだけですO(k*2^k * (n/k)^k * 2^n)。

kが制限されている場合は、大きなO表記で式からも削除でき、。を取得しO(n^k* 2^n)ます。この場合でも、をn^k << 2^n無視することはできません。定数cごとに、のようnなものが存在するc*2^n < n^k *2^nため、アルゴリズムはO(2^n)1ではないことに注意してください。

加算に関しては、小さな要素は無視できます。その場合k < n、すべての：のようなO(n + k) = O(n)定数があるためですが、これはもちろん、製品を扱う場合には当てはまりません。c,Nn > Nc*n < n + k

于 2012-07-03T15:50:11.153 に答える