Vereinfachung der Big-O-Komplexität dieses Exponentialalgorithmus

Question

Ich habe einen Zählalgorithmus, für den ich versuche, eine allgemeine Big-O-Beschreibung zu erhalten. Es ist schrecklich verschachtelt und furchtbar exponentiell. Hier ist sie:

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. 

Hier ist eine line-by-line Idee jeder Laufzeit

1. Dies ist eine einfache Partitionierung und ich werde einfach eine Konstante c1 geben.
2. max_k ist eine kleine Zahl, immer kleiner als n, vielleicht etwa 4 oder 5. Ich werde k unten verwenden.
3. Diese Schleife läuft immer 2^k * (n wähle k) mal
4. Indem wir Linie 1 konstant betrachten, können wir diese Linie verallgemeinern und wissen, dass sie im schlimmsten Fall nie mehr als 2^n Mal feuern wird Im Allgemeinen wird ein Bruchteil von 2^n Mal ausgeführt, also werden wir dies eine nennen (2^n)/c2
5. Dies ist die einfache if-Anweisung in allen diesen Schleifen, also c3.

Multipliziert man alles zusammen ergibt:

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

Da ich eine Big-O-Darstellung wollen, gibt Konstanten ignoriert:

begrenzt ist

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

Es ist bekannt, dass (n wählen k) oben durch (n * e/k)^k, so:

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

Meine Frage darauf ist, was kann ich hier ignorieren ... 2^n ist sicherlich der dominierende Begriff, da n immer größer als k ist, und typischerweise viel mehr. Kann dies zu O (2^n) vereinfacht werden? Oder O (2^schrecklich)? Oder sollte ich im 2^k wie in O (2^k * 2^n) gehen? (oder lassen Sie alle Begriffe drin?)

Mein Verständnis ist, dass, wenn k oder max_k kann konkurrieren oder übertreffen n, dann sind sie von entscheidender Bedeutung. Aber da sie immer beherrscht werden, können sie wie die Polynom-Laufzeiten niedrigerer Ordnung verworfen werden? Ich nehme an, dass die ganze exponentielle Laufzeit Verwirrung mich verwirrt. Jeder Rat wird sehr geschätzt.

Answer 1

Mein Verständnis ist, dass, wenn k oder max_k kann n konkurrieren oder übertreffen, dann sie

Zwar sind von entscheidender Bedeutung, aber umgekehrt nicht ist - das heißt - es ist nicht außer Acht gelassen werden kann, wenn kommt zu großer O-Notation, auch wenn es nicht mit n konkurriert. Es kann nur ignoriert werden, wenn max_k mit einer Konstante begrenzt ist (es gibt eine Konstante c, so dass k <= c). Zum Beispiel - O(n * logk) Algorithmen, sind nicht O(n), da der k-Faktor nicht begrenzt ist und somit existiert eine k so dass für jede Konstante c.

Da der Ausdruck, den Sie haben, ein Produkt ist, können Sie alles ignorieren Konstanten, die in Ihrem Fall - nur e bekommen Sie O(k*2^k * (n/k)^k * 2^n).

Wenn k ist begrenzt, dann können Sie es aus dem Ausdruck entfernen als auch in O-Notation, und Sie werden O(n^k* 2^n) erhalten.Beachten Sie, dass auch in diesem Fall, obwohl n^k << 2^n, kann immer noch nicht ignoriert werden, da für jede Konstante c gibt es einige n so dass c*2^n < n^k *2^n, so dass der Algorithmus ist kein O(2^n) man.

Kleinere Faktoren können bei der Addition ignoriert werden. Wenn k < n dann O(n + k) = O(n), denn es gibt eine Konstanten so dass für alle n > N: c*n < n + k, aber das ist natürlich nicht wahr, wenn es um das Produkt handelt.