Permutationen Laufzeitanalyse: Iterative DP Lösung

Question

Meine iterative DP Lösung wird wie folgt dar:

def permutations(string): 
    # let n = len(string) 
    N = [[] for _ in range(len(string) + 1)] # O(n) 

    N[0].append("") 

    for i in range(1, len(string) + 1): # O(n) 
     N[i] = [perm[:j] + string[i - 1] + perm[j:] for j in range(i) for perm in N[i - 1]] # O(???) 

    return N[-1] 

Aber ich habe Probleme mit der Laufzeit des obigen Programms zu analysieren. Insbesondere begrenzt die Laufzeit der Linie for perm in N[i - 1]. Ich bin mir bewusst, dass die rekursive Lösung O(n!) ist, aber wie können wir die Laufzeit des obigen Programms finden, ohne auf die rekursive Laufzeit zu vertrauen?

Answer 1

die

N[i] = [perm[:j] + string[i - 1] + perm[j:] for j in range(i) for perm in N[i - 1]] 

als unser Hauptinteresse Lassen betrachten. Jetzt

Wir können es umschreiben als

line 1: for i in range(1, len(string) + 1):      # O(n) 
line 2:  N[i] = []           # O(n) 
line 3:  for j in range(i):         # O(sum i from 1 to n) 
line 4:   for perm in N[i - 1]:       # O(sum len(Ni) from 1 to n) 
line 5:    N[i].append(perm[:j] + string[i - 1] + perm[j:]) 

, für i = 1, line 3 und line 4 ein einziges Mal laufen würde, N[1] mit einem einzigen Element string[0] verlassen.

Für i = 2 würde line 3 zweimal laufen und line 4 würde ein einziges Mal für den ersten Lauf und 2 für den zweiten Lauf, N[2] mit drei Elementen zu verlassen.

Das Muster sehen? lässt schnell vorspulen. 6, 24, 120, 720.

N total runs diff 
1 1   1 
2 3   2 
3 9   6 
4 33   24 
5 153   120 
... 

So erhalten wir eine Gesamtkomplexität von

n 
____ 
\ 
    > k! 
/___ 
k = 0  (asciiart courtesy of sympy) 

Vereinfachen es ziemlich kompliziert ist (https://math.stackexchange.com/questions/227551/), aber wir können versichern, dass es innerhalb der O(n!) Grenze ist, da die Summierung von k*k! von 1 bis n ist (n+1)! - 1, so dass wir eine Gesamtlaufzeit von O(n!), erhalten, ohne auf die bekannte rekursive Laufzeit angewiesen zu sein.