Big-O-Zeit Komplexität des rekursiven Algorithmus mit verschachtelten For-Schleifen

Question

Ich habe einen rekursiven Algorithmus mit zwei verschachtelten For-Schleifen. Ich versuche herauszufinden, wie groß die Komplexität von Big-O sein wird.

public Set<Person> getDistinctCombinedPersons(Collection<Person> persons) { 
    return permutatePersons(new ArrayList(persons), new HashSet<>(persons)); 
} 

---

private Set<Person> permutatePersons(List<Person> personList, Set<Person> personSet) { 
    if(personList.isEmpty() { 
    return personSet; 
    } 

    Set<Person> deepCopyPersonSet = new HashSet<>(personSet); 

    for(Person lPerson : personList) { 
    for(Person sPerson : deepCopyPersonSet) { 
     Person uniquePerson = CombinePeople.combine(lPerson, sPerson); 
     personSet.add(uniquePerson); 
    } 
    } 

    personList.remove(personList.size()-1); 

    return permutatePersons(personList, personSet); 
} 

Answer 1

Unter der Annahme, dass Sie permutatePersons mit einer Liste der Länge N die folgende Rekursion gilt nennen:

Das ist, weil Sie in jedem rekursiven Schritt Funktion mit Liste der Länge N-1 aufrufen (wobei N der aktuelle Länge) und auch Berechnungen der Gesamtkomplexität O (N^2) (äußere Schleife O (N) -just traversierende Liste und innere Schleife durchlaufen die Hash-Karte in O (N) -O (1) für jedes Element und insgesamt N Element, also sind die verschachtelten Schleifen insgesamt O (N^2)). siehe

können Sie leicht:

T(N) = T(N-1) + O(N^2) = T(N-2) + O(N^2) + O((N-1)^2) =... 

= O(n(n+1)(2n+1)/6) = O(n^3) 

Answer 2

sieht aus wie ein Big-O von n^2 für die verschachtelte Schleife sein würde:

for(Person lPerson : personList) { 
    for(Person sPerson : deepCopyPersonSet) { 
     Person uniquePerson = CombinePeople.combine(lPerson, sPerson); 
     personSet.add(uniquePerson); 
    } 
    } 

Sie müssen für jedes Element über die jedes Element iterieren in der Satz.

Und dann hat der rekursive Aufruf einen großen O von n, da er Ihre Methode einmal für jedes Element in der Menge aufruft.

Die Kombination der beiden: n * n^2 in einem großen O von n führen^3

Answer 3

Weil Sie zwei verschachtelte Schleifen haben haben Sie die Laufzeitkomplexität von O(m*n). Es ist, weil für n - Person s in deepCopyPersonSet Sie iterieren m mal. n In diesem Beispiel ist die Menge Person s in personList.

Ihr Code ist im Grunde:

for(int i = 0, i < m, i++) 
    for(int j = 0, j < n, j++) 
    //your code 

Für jede Iteration m, wir haben n Iterationen Code