Hola usuario de nuestra página, tenemos la solución a lo que buscabas, continúa leyendo y la obtendrás a continuación.
Solución:
La solución recursiva tiene una complejidad de O(n!) ya que se rige por la ecuación: T(n) = n * T(n-1) + O(1).
La solución iterativa tiene tres bucles anidados y, por lo tanto, tiene una complejidad de O(n^3).
Sin embargo, la solución iterativa no producirá permutaciones correctas para ningún número aparte de 3.
Para n = 3puedes ver eso n * (n - 1) * (n-2) = n!. El LHS es O(n^3) (o mejor O(n^n) ya que n=3 aquí) y el RHS es O(n!).
Para valores más grandes del tamaño de la lista, digamos npodrías tener n bucles anidados y eso proporcionará permutaciones válidas. La complejidad en ese caso será O(n^n)y eso es mucho más grande que O(n!)o mejor, n! < n^n. Hay una relación bastante agradable llamada aproximación de Stirling que explica esta relación.
Es el producción (que es enorme) importa en este problema, no la implementación de la rutina. Para n artículos distintos, hay n! permutaciones que se devolverán como la respuesta, y así tenemos al menos O(n!) complejidad.
Con ayuda de la aproximación de Stirling
O(n!) = O(n^(1/2+n)/exp(n)) = O(sqrt(n) * (n/e)^n)
podemos ver fácilmente que O(n!) > O(n^c) por ninguna constante cpor eso no importa si la implementación misma agrega otro O(n^3) ya que
O(n!) + O(n^3) = O(n!)