2^n algoritmo de complejidad

Question

Necesito implementar y probar un algoritmo con una complejidad 2^n. He estado tratando de encontrar uno por un tiempo. Si hay alguna manera de lograr esto mediante la implementación, con una complejidad exacta de 2^n sería óptimo. Si alguien sabe de una ubicación, puedo encontrar un ejemplo o podría ayudarme a implementar una, sería genial :-). La operación básica puede ser cualquier cosa, pero una sola declaración como i ++; sería lo mejor

Answer 1

Genera todos los subconjuntos de un conjunto con n elementos.

Agregado. La manera más simple de generar todos los subconjuntos de S = {a0, a1, ..., an-1} es probablemente traducir entre la representación binaria del rango y el subconjunto.

Tome S = {a0, a1, a2}.

rank binary subset 
0 000 {} 
1 001 {a0} 
2 010 {a1} 
3 011 {a0, a1} 
4 100 {a2} 
5 101 {a0, a2} 
6 110 {a1, a2} 
7 111 {a0, a1, a2} 

Entonces, un 1 en el binario significa que el elemento correspondiente está en el subconjunto. A 0 significa que el elemento no está en el subconjunto.

Pero también debe buscar el código Gray.

Answer 2

El cálculo del número de Fibonacci recursivo clásico es O (2^n).

unsigned Fib(unsigned n) 
{ 
    if (n <= 1) 
     return n; 
    else 
     return Fib(n - 1) + Fib(n - 2); 
} 

---

Dado lo anterior es en realidad theta (Phi^n), que estoy añadiendo un theta (2^n) algoritmo que volver 2^n. Gracias a Jeremiah Willcock.

unsigned TwoExp(unsigned n) 
{ 
    if (n == 0) 
     return 1; 
    else 
     return TwoExp(n - 1) + TwoExp(n - 1); 
} 

Answer 3

Aquí hay una: muestra los dígitos de 2^(2^n).

Answer 4

Quantum Bogosort tiene 2^n space complexity.

Answer 5

Pasé una gran cantidad de tiempo reconsiderando el problema y me gustaría publicar una solución que se me ocurrió. Todas las respuestas contribuyeron a mi capacidad para llegar a esta solución, y estoy muy agradecido por todos los que respondieron. :-) Me doy cuenta de que el algoritmo no hace prácticamente nada.

está escrito en Java
parece que no puede conseguir las pestañas para trabajar
funcionamiento básico es i ++;

public class TwoToTheN 
{ 
    private static int twoToTheN = 0; 
    private static int power = 3; 

    public static void main(String[] args) 
    { 
     twoToTheN(power); 
     System.out.println(twoToTheN); 
    } 

    private static void twoToTheN(int n) 
    { 
     if(n == 0) 
     { 
      twoToTheN++; 
      return; 
     } 
     else if(n == 1) 
     { 
      twoToTheN++; 
      twoToTheN++; 
      return; 
     } 
     twoToTheN(n-1); 
     twoToTheN(n-1); 
    } 
}