algorithm - que - operaciones con factoriales

Ejemplo de un algoritmo de tiempo factorial O(n!)

Question

Estoy estudiando la complejidad del tiempo en la escuela y nuestro foco principal parece ser el tiempo polinomial algoritmos y tiempo cuasi lineal algoritmos con el tiempo exponencial ocasional algoritmo como un ejemplo de la perspectiva de tiempo de ejecución. Sin embargo, lidiar con complejidades de tiempo más grandes nunca fue cubierto.

Me gustaría ver un problema de ejemplo con una solución algorítmica que se ejecuta en tiempo factorial . El algoritmo puede ser un enfoque ingenuo para resolver un problema, pero no puede inflarse artificialmente para funcionar en tiempo factorial.

Verificación de calle adicional si el algoritmo de tiempo factorial es el algoritmo mejor conocido para resolver el problema.

Answer 1

Genera todas las permutaciones de una lista

Tienes n! listas, por lo que no puede lograr una mejor eficiencia que O(n!) .

Answer 2

Listar todas las permutaciones de una matriz es O (n!). A continuación se muestra una implementación recursiva utilizando el método de intercambio. La recursión está dentro del ciclo for y los elementos de la matriz se intercambian en su posición hasta que no quedan más elementos. Como puede ver en el recuento de resultados, la cantidad de elementos en la matriz es n !. Cada permutación es una operación y hay n! operaciones.

def permutation(array, start, result)
    if (start == array.length) then
        result << array.dup  
    end
    for i in start..array.length-1 do
        array[start], array[i] = array[i], array[start]
        permutation(array, start+1,result)
        array[start], array[i] = array[i], array[start]
    end 
    result   
end        


p permutation([1,2,3], 0, []).count  #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!

Answer 3

¡Traveling Salesman tiene una solución ingenua que es O (n!), Pero tiene una solución de programación dinámica que es O (n ^ 2 * 2 ^ n)