algorithm - keywords - Ejemplo de Big O de 2 ^ n

meta tags generator

Question

Así que puedo imaginar lo que es un algoritmo que tiene una complejidad de n ^ c, solo el número de anidados para bucles.

for (var i = 0; i < dataset.len; i++ {
    for (var j = 0; j < dataset.len; j++) {
        //do stuff with i and j
    }
}

El registro es algo que divide el conjunto de datos en la mitad cada vez, la búsqueda binaria hace esto (no del todo seguro de cómo se ve este código).

Pero, ¿cuál es un ejemplo simple de un algoritmo que es c ^ n o más específicamente 2 ^ n? ¿Está O (2 ^ n) basado en bucles a través de datos? ¿O cómo se dividen los datos? ¿O algo completamente distinto?

Answer 1

Aquí hay dos ejemplos simples en python con Big O / Landau (2 ^ N):

#fibonacci 
def fib(num):    
    if num==0 or num==1:
        return num
    else:
        return fib(num-1)+fib(num-2)

num=10
for i in range(0,num):
    print(fib(i))


#tower of Hanoi
def move(disk , from, to, aux):
    if disk >= 1:
        # from twoer , auxilart 
        move(disk-1, from, aux, to)
        print ("Move disk", disk, "from rod", from_rod, "to rod", to_rod)
        move(disk-1, aux, to, from)

n = 3
move(n, ''A'', ''B'', ''C'')

Answer 2

Aquí hay un clip de código que calcula la suma de valores de cada combinación de valores en una matriz de bienes (y el value es una variable de matriz global):

fun boom(idx: Int, pre: Int, include: Boolean) {
    if (idx < 0) return
    boom(idx - 1, pre + if (include) values[idx] else 0, true)
    boom(idx - 1, pre + if (include) values[idx] else 0, false)
    println(pre + if (include) values[idx] else 0)
}

Como puedes ver, es recursivo. Podemos insertar bucles para obtener complejidad Polynomial y usar recursivo para obtener complejidad Exponential .

Answer 3

Los algoritmos con tiempo de ejecución O (2 ^ N) a menudo son algoritmos recursivos que resuelven un problema de tamaño N al resolver recursivamente dos problemas más pequeños de tamaño N-1.

Este programa, por ejemplo, imprime todos los movimientos necesarios para resolver el famoso problema "Torres de Hanoi" para N discos en pseudo-código

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg)
{
    if (N<1) {
        return;
    }
    if (N>1) {
        solve_hanoi(N-1, from_peg, spare_peg, to_peg);
    }
    print "move from " + from_peg + " to " + to_peg;
    if (N>1) {
        solve_hanoi(N-1, spare_peg, to_peg, from_peg);
    }
}

Deje que T (N) sea el tiempo necesario para los N discos.

Tenemos:

T(1) = O(1)
and
T(N) = O(1) + 2*T(N-1) when N>1

Si expandes repetidamente el último término, obtienes:

T(N) = 3*O(1) + 4*T(N-2)
T(N) = 7*O(1) + 8*T(N-3)
...
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1)
T(N) = (2^N - 1)*O(1)
T(N) = O(2^N)

Para resolver esto, solo hay que saber que ciertos patrones en la relación de recurrencia conducen a resultados exponenciales. Generalmente T(N) = ... + C*T(N-1) con C > 1 significa O (x ^ N). Ver:

https://en.wikipedia.org/wiki/Recurrence_relation

Answer 4

Piense, por ejemplo, en iterar sobre todos los subconjuntos posibles de un conjunto. Este tipo de algoritmos se utiliza, por ejemplo, para un problema generalizado de mochila.

Si le resulta difícil entender cómo la iteración sobre subconjuntos se traduce a O (2 ^ n), imagine un conjunto de n interruptores, cada uno de ellos correspondiente a un elemento de un conjunto. Ahora, cada uno de los interruptores se puede activar o desactivar. Piense en "on" como si estuviera en el subconjunto. Note, cuántas combinaciones son posibles: 2 ^ n.

Si quieres ver un ejemplo en código, aquí es generalmente más fácil pensar en recursión, pero no puedo pensar en ningún otro ejemplo agradable y que no se pueda entender en este momento.

Answer 5

c ^ N = Todas las combinaciones de n elementos de un alfabeto de tamaño c .

Más específicamente, 2 ^ N son todos los números representables con N bits.

Los casos comunes se implementan recursivamente, algo como:

vector<int> bits;
int N
void find_solution(int pos) {
   if (pos == N) {
     check_solution();
     return;
   }
   bits[pos] = 0;
   find_solution(pos + 1);
   bits[pos] = 1;
   find_solution(pos + 1);
}

Answer 6

  int Fibonacci(int number)
 {
  if (number <= 1) return number;

  return Fibonacci(number - 2) + Fibonacci(number - 1);
 }

El crecimiento se duplica con cada adición al conjunto de datos de entrada. La curva de crecimiento de una función O (2N) es exponencial: comienza muy superficialmente y luego asciende de forma meteorológica. Mi ejemplo de gran O (2 ^ n), pero mucho mejor es este:

public void solve(int n, String start, String auxiliary, String end) {
   if (n == 1) {
       System.out.println(start + " -> " + end);
   } else {
       solve(n - 1, start, end, auxiliary);
       System.out.println(start + " -> " + end);
       solve(n - 1, auxiliary, start, end);
   }

En este método, el programa imprime todos los movimientos para resolver el problema "Torre de Hanoi". Ambos ejemplos utilizan el uso recursivo para resolver el problema y tuvieron un gran tiempo de ejecución O (2 ^ n).