Simplificando la Complejidad Big-O de este Algoritmo Exponencial

Question

Tengo un algoritmo de conteo para el cual estoy tratando de obtener una descripción general de gran. Está horriblemente anidado y terriblemente exponencial. Aquí 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. 

aquí es una idea, línea por línea de cada tiempo de funcionamiento

1. Se trata de una partición simple y voy a darle un solo c1 constante.
2. max_k es un número pequeño, siempre menor que n, tal vez alrededor de 4 o 5. Utilizaré k a continuación.
3. Este bucle siempre ejecuta 2^k * (n elige k) veces
4. Al considerar constante la línea 1, podemos generalizar esta línea y saber que nunca disparará más de 2^n veces en total en el peor de los casos, pero generalmente se ejecutará una fracción de 2^n veces, así que llamaremos a esto (2^n)/c2
5. Esta es la operación simple de instrucción if dentro de todos estos bucles, por lo que c3.

Multiplicando todos estos juntos da:

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

Ya que quiero una representación grande-O, haciendo caso omiso de las constantes da:

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

Se sabe que (n elegir k) está delimitada arriba por (n * e/k)^k, entonces:

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

Mi questi es, lo que puedo ignorar aquí ... 2^n es sin duda el término dominante, ya que n siempre es más grande que k, y típicamente mucho más. ¿Puede esto simplificarse a O (2^n)? O O (2^terrible)? ¿O debería dejar en el 2^k, como en O (2^k * 2^n)? (o deje todos los términos en?)

Tengo entendido que si k o max_k pueden competir o superar n, entonces son vitales. Pero dado que siempre están dominados, ¿pueden descartarse como términos de orden inferior de tiempos de ejecución polinómica? Supongo que todo el lío de tiempo de ejecución exponencial me está confundiendo. Cualquier consejo es muy apreciado.

Answer 1

Mi opinión es que si k o max_k pueden competir o superar n, entonces que son vitales

Es cierto, pero a la inversa no es - es decir - que no puede ser ignorado cuando se llega a la notación O grande, incluso si no compite con n. Se puede ignorar solo si max_k está limitado con una constante (hay una constante c tal que k <= c). Por ejemplo, los algoritmos O(n * logk), no son O(n), ya que el factor k no está limitado y, por lo tanto, existe un k tal que nlogk > c*n por cada constante c.

Dado que la expresión que obtuvo es un producto, todo lo que puede ignorar son las constantes, que en su caso - es solo e consiguiendo O(k*2^k * (n/k)^k * 2^n).

Si es k delimitada, a continuación, puede eliminarlo de la expresión, así como en la notación O grande, y obtendrá O(n^k* 2^n).Tenga en cuenta que incluso en este caso, aunque n^k << 2^n, aún no puede ignorarse, porque para cada constante c existe algo de n tal que c*2^n < n^k *2^n, por lo que el algoritmo no es O(2^n).

Los factores más pequeños se pueden ignorar cuando se trata de la adición. Si k < n entonces O(n + k) = O(n), porque hay una constantes c,N tal que para todos n > N: c*n < n + k, pero esto por supuesto no es cierto cuando se trata de productos.