Problema: dada una matriz de números de enteros distintos, devuelve todas las permutaciones posibles.

Por ejemplo, [1,2,3] tiene las siguientes permutaciones: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3 ,1,2], [3,2,1] ].

Esta es mi implementación de javascript, similar a la solución estándar para este problema. Encontré muchos lugares diciendo que esta complejidad de tiempo debe ser T(n*n!). Pero según tengo entendido, debería ser T((n!)^2). Nuevamente puedo estar equivocado!!.

Solución JavaScript

 var permute = function(nums) { if(nums.length === 0) return []; if(nums.length ===1){ return [[...nums]]; } let results = []; const len = nums.length; for(let i=0; i<len; i++){ // eg: [1,2,3,4] const temp = nums[i]; nums[i] = nums[len-1]; nums[len-1] = temp; // [4,2,3,1] const n = nums.pop(); // [4,2,3] const prems = permute(nums); prems.forEach(perm => perm.push(n)); results = results.concat(prems); nums.push(nums[i]) // [4,2,3,4] nums[i] = temp; // [1,2,3,4] } return results; };

Así es como obtuve la respuesta como T((n!)^2)

así que para el exterior,

1ra iteración

• Cada iteración hará una llamada recursiva con una matriz de elementos n-1
• ¡Entonces los resultados, que serán todas las permutaciones con n-1 elementos, serán de tamaño (n-1)!
• ¡Así que tenemos que recorrer (n-1)! elementos para agregar el elemento reventado.

Para iteraciones

Entonces, para la primera llamada recursiva, esto sucederá n veces (el ciclo externo va de 0 a n)

Entonces, para la primera llamada recursiva T-(n*(n-1)!)

Dado que el tamaño del árbol de recurrencia es n! la complejidad de tiempo final debería ser - T(n! n (n-1)!) = T((n!)^2).

Me estoy perdiendo de algo ??