Simplification de la complexité Big-O de cet algorithme exponentiel

Question

J'ai un algorithme de comptage pour lequel j'essaie d'obtenir une description générale de big-o. Il est horriblement niché et horriblement exponentiel. Ici, il est:

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. 

Voici une ligne par ligne idée de chaque durée

1. Ceci est une partition simple et je vais juste donner une c1 constante. Max_k est un petit nombre, toujours inférieur à n, peut-être autour de 4 ou 5. Je vais utiliser k ci-dessous. En considérant la ligne 1 constante, on peut généraliser cette ligne et savoir qu'elle ne se déclenchera jamais plus de 2^n fois au total dans le pire des cas, mais généralement une fraction de 2^n fois, donc nous appellerons celui-ci (2^n)/c2
2. Ceci est l'opération simple if-instruction à l'intérieur de toutes ces boucles, donc c3.

Multipliant tous ces ensemble donne:

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

Depuis que je veux une représentation grand-O, en ignorant les constantes donne:

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

On sait que (choisir n k) est limitée ci-dessus par (n * e/k)^k, donc:

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

Mes questions on est, que puis-je ignorer ici ... 2^n est certainement le terme dominant puisque n est toujours plus grand que k, et typiquement beaucoup plus. Est-ce que cela peut être simplifié en O (2^n)? Ou O (2^terrible)? Ou devrais-je laisser dans le 2^k, comme dans O (2^k * 2^n)? (ou laisser tous les termes dans?)

Ma compréhension est que si k ou max_k peut rivaliser ou dépasser n, alors ils sont vitaux. Mais puisqu'ils sont toujours dominés, peuvent-ils être rejetés comme des termes inférieurs d'ordre polynomial? Je suppose que tout le désordre du temps de fonctionnement exponentiel me confond. Tout conseil est grandement appréciée.

Answer 1

Ma compréhension est que si k ou max_k peuvent rivaliser ou dépasser n, ils sont essentiels

est vrai, mais l'inverse est pas - ce qui signifie - il ne peut pas être ignoré quand il vient à la grande notation O, même si elle ne fait pas concurrence à n. Il peut être ignoré seulement si max_k est borné avec une constante (il y a une constante c telle que k <= c). Par exemple - O(n * logk) algorithmes, ne sont pas O(n), puisque le facteur k n'est pas borné et donc il existe un k tel que nlogk > c*n pour chaque constante .

Puisque l'expression que vous avez est un produit, tout ce que vous pouvez ignorer sont des constantes, qui dans votre cas - est seulement e vous obtenant O(k*2^k * (n/k)^k * 2^n).

Si k est limitée, vous pouvez le supprimer de l'expression aussi bien dans la notation grand O, et vous obtiendrez O(n^k* 2^n).Notez que même dans ce cas, bien que n^k << 2^n, il ne peut toujours pas être ignoré, car pour chaque constante c existe n tels que c*2^n < n^k *2^n, donc l'algorithme n'est pas un O(2^n).

De plus petits facteurs peuvent être ignorés quand il s'agit de l'addition. Si k < n alors O(n + k) = O(n), parce qu'il ya une constantes c,N tel que pour tous n > N: c*n < n + k, mais ce n'est bien sûr pas vrai lorsqu'il s'agit de produit.