¿Cuál sería la complejidad temporal de este algoritmo de retroceso para encontrar permutaciones?
Estoy tratando de determinar la complejidad temporal y espacial de este algoritmo que creé para encontrar todas las permutaciones de una matriz en Python. ¿Es la complejidad temporal O(sum_{k=1}^N P(n,k)), donde P(n,k) es una permutación con k factores?
class Solution:
def permute(self, vals):
answer = [vals]
def backtrack(i, curr_arr):
if i >= len(vals):
return
curr_val = curr_arr[i]
for j in range(i + 1, len(vals)):
permutation = curr_arr.copy()
temp_val = curr_arr[j]
permutation[j] = curr_val
permutation[i] = temp_val
answer.append(permutation)
backtrack(i + 1, permutation)
backtrack(i + 1, curr_arr)
backtrack(0, vals)
return answer
davy.ai
La complejidad temporal de este algoritmo es O(n!). Esto se debe a que el algoritmo genera todas las posibles permutaciones del arreglo intercambiando elementos de forma recursiva. El número de permutaciones posibles para un arreglo de longitud n es n!, que es el factorial de n.
En cuanto a la complejidad espacial, es O(n!), que es la cantidad de permutaciones generadas. La lista de respuestas almacena todas estas permutaciones, por lo que su tamaño es O(n!). La función de retroceso recursivo también utiliza una pila de llamadas, que tiene una complejidad espacial de O(n). Por lo tanto, la complejidad espacial total es O(n!) + O(n), que se simplifica a O(n!).