Complejidad temporal de generar todas las posibles permutaciones utilizando la técnica de retroceso (comparación de 2 soluciones)
Enfoque 1:
Aquí podemos ver la ecuación de recurrencia, que es T(N) = N * T(N-1) + c, por lo que la complejidad de tiempo final resulta ser O(N!), lo cual tiene sentido.
Enfoque 2:
La diferencia entre este código y el enfoque 1 es que estamos realizando un trabajo innecesario cada vez (cuando chosen[i] es verdadero, continuamos en lugar de avanzar en el árbol de recursión).
Creo que la relación de recurrencia aquí debería ser T(N) = N * T(N-1) + N * c, ya que podemos dividir el bucle for en 2 partes: una en la que hacemos un trabajo constante en cada iteración (N * c) y otra en la que hacemos llamadas recursivas (N * T(N-1)). Luego, para T(N-1) = (N-1) * T(N-2) + N*c (nota que todavía estamos pagando el costo N * c aquí) y así sucesivamente. Al final, nos quedará un término de N^N que dominará a O(N!) para valores grandes de N. ¿Entonces esto significa que la complejidad de tiempo del segundo código es O(N^N) y no O(N!)?
Pregunta relacionada:
Para el problema de las N reinas, tenemos una solución de retroceso (se puede consultar en https://dev.to/chengmuy/optimizing-an-n-queens-solution-3m1m), pero aquí tenemos un bucle for que verifica si el estado actual es seguro o no (en un tiempo promedio de O(1)) y realiza llamadas recursivas en consecuencia. A menos que esté equivocado, la complejidad de tiempo de esta solución de retroceso también es O(N!). Pero, estoy confundido acerca de cómo tener en cuenta el costo de las ramas que se terminan tempranamente en O(N!), es decir, básicamente el costo de tener que verificar todas las filas para la columna actual (o columnas para la fila actual, dependiendo de la implementación) que son seguras cada vez.
davy.ai
Explicación de la complejidad temporal de los algoritmos de permutación
Enfoque 1:
El primer enfoque utiliza llamadas recursivas para generar todas las permutaciones de una cadena dada. En cada llamada recursiva, el algoritmo genera una permutación de la cadena de longitud N. La complejidad temporal de este enfoque se puede calcular utilizando la siguiente relación recurrente:
T(N) = N * T(N-1) + c
La relación anterior establece que la complejidad temporal de generar todas las permutaciones de una cadena de longitud N es igual a la complejidad temporal de generar todas las permutaciones de una cadena de longitud N-1 multiplicada por N, más algunos cálculos constantes c. El caso base para esta relación recurrente es T(1) = 1, ya que solo hay una permutación de una cadena de longitud 1.
Resolviendo la relación recurrente anterior, obtenemos:
T(N) = N * (N-1) * (N-2) * … * 2 * 1 = N!
Por lo tanto, la complejidad temporal del Enfoque 1 es O(N!), lo cual tiene sentido.
Enfoque 2:
El segundo enfoque es similar al primer enfoque, pero verifica si un carácter ya ha sido elegido antes de elegirlo. Si un carácter ya ha sido elegido, se salta ese carácter y pasa al siguiente. Esto conduce a un trabajo desperdiciado, ya que no genera permutaciones válidas al omitir caracteres innecesariamente.
La complejidad temporal del segundo enfoque se puede calcular utilizando una relación recurrente similar:
T(N) = N * T(N-1) + N * c
Aquí, la primera parte de la relación recurrente es la misma que antes, generar todas las permutaciones de una cadena de longitud N-1. Sin embargo, en la segunda parte, debemos iterar a través de la cadena de longitud N-1 para verificar qué caracteres ya han sido elegidos, y esto lleva N pasos cada vez. Por lo tanto, la complejidad temporal total del bucle es N * c.
Resolviendo la relación recurrente anterior, obtenemos:
T(N) = N! * N
Por lo tanto, la complejidad temporal del Enfoque 2 es O(N * N!), que todavía está dominado por O(N!) para valores grandes de N.
Problema de las N Reinas
El problema de las N Reinas es un famoso ejemplo de un algoritmo de retroceso. El objetivo es colocar N reinas en un tablero de ajedrez de tamaño N x N de manera que ninguna de ellas amenace a las demás. Una forma de resolver este problema es mediante el retroceso: intentamos colocar una reina en cada casilla del tablero, y si se puede colocar una reina, pasamos a la siguiente fila. Si en algún momento no podemos colocar una reina, volvemos atrás a la fila anterior y probamos en una casilla diferente.
La complejidad temporal de este algoritmo se puede calcular utilizando una relación recurrente similar:
T(N) = N * T(N-1) + N^2
Aquí, la primera parte de la relación recurrente es la complejidad temporal de colocar una reina en el tablero, y la segunda parte es la complejidad temporal de verificar si se puede colocar una reina de manera segura en una posición dada.
La complejidad temporal en el peor de los casos del problema de las N Reinas es O(N!), que es la misma que en el primer enfoque para generar permutaciones. Sin embargo, en la práctica, el algoritmo realiza retrocesos tempranos y poda muchas ramas del árbol de búsqueda, por lo que la complejidad temporal real es mucho menor.
Para tener en cuenta el costo de las ramas terminadas tempranamente en O(N!), podemos utilizar una técnica llamada análisis del caso promedio. Para esto, asumimos que la colocación de reinas en el tablero es aleatoria y calculamos el número promedio de nodos visitados en el árbol de búsqueda. Se ha demostrado que la complejidad temporal en el caso promedio del problema de las N Reinas es O(N^(3/2)) utilizando este enfoque.