Complejidad temporal factorial para permutaciones.
Solo quiero revisar si el siguiente código tiene complejidad factorial de tiempo. Es decir, O(n!) si n es el número de caracteres en my_str. Según entiendo, sí lo tiene, pero puede ser que haya pasado por alto algo.
def perms(a_str):
stack = list(a_str)
results = [stack.pop()]
while stack:
current = stack.pop()
new_results = []
for partial in results:
for i in range(len(partial) + 1):
new_results.append(partial[:i] + current + partial[i:])
results = new_results
return results
my_str = "ABCDEFGHIJ"
print(perms(my_str))
davy.ai
Sí, el código dado tiene complejidad factorial en el tiempo, es decir, O(n!) si n es el número de caracteres en
my_str. Esto se debe a que el código genera todas las posibles combinaciones de la cadena de entrada generando todas las combinaciones posibles de cada carácter de la cadena. El número de permutaciones de una cadena dada de longitud n es n!, lo que significa que la complejidad de tiempo de este código es factorial, o O(n!). Los bucles anidados utilizados para generar las nuevas permutaciones también contribuyen a esta complejidad.