Geben Sie eine gegebene Anzahl von eindeutigen Zahlen zurück und geben Sie alle möglichen Permutationen zurück.
Zum Beispiel haben [1,2,3] die folgenden Permutationen:
1,2,3, 1,3,2, 2,1,3, 2,3,1, 3,1,2, 3,2,1] / p>
Meine iterative Lösung ist:
%Vor%Meine rekursive Lösung ist:
%Vor% Nach meiner Aussage ist die Zeitkomplexität (big-Oh) meiner iterativen Lösung: n * n (n + 1) / 2 ~ O (n ^ 3)
Ich bin nicht in der Lage, die zeitliche Komplexität meiner rekursiven Lösung herauszufinden
Kann jemand die Komplexität beider erklären?
Die rekursive Lösung hat eine Komplexität von O(n!) , da sie von der folgenden Gleichung bestimmt wird: T(n) = n * T(n-1) + O(1) .
Die iterative Lösung hat drei verschachtelte Schleifen und hat daher eine Komplexität von O(n^3) .
Die iterative Lösung erzeugt jedoch keine korrekten Permutationen für eine beliebige Zahl außer 3 .
Für n = 3 können Sie n * (n - 1) * (n-2) = n! sehen. Die LHS ist O(n^3) (oder vielmehr O(n^n) seit n=3 hier) und die RHS ist O(n!) .
Für größere Werte der Größe der Liste, sagen wir n , könnten Sie n verschachtelte Schleifen haben, die gültige Permutationen liefern. Die Komplexität in diesem Fall ist O(n^n) , und das ist viel größer als O(n!) , oder besser gesagt, n! < n^n . Es gibt eine ziemlich nette Beziehung namens Stirling's Approximation , die diese Beziehung erklärt.
Es ist die Ausgabe (die sehr groß ist), die bei diesem Problem eine Rolle spielt, nicht die Implementierung der Routine. Für n distinct-Elemente gibt es n! permutations, die als Antwort zurückgegeben werden, und somit haben wir mindestens O(n!) complexity.
Mit Hilfe von Stirlings Annäherung
%Vor% wir können leicht sehen, dass O(n!) > O(n^c) für jede Konstante c ist, deshalb ist es egal, ob die Implementierung selbst ein weiteres O(n^3) seit
Tags und Links algorithm java recursion time-complexity