Was die Zeitkomplexität des folgenden Algorithmus ist

Question

Die Frage

Ich habe Probleme beim Finden der Zeit Komplexität des folgenden Algorithmus: Mein Problem

void f2(int n) { 
    int i; 
    if (n == 1) { 
     return; 
    } 
    for (i = 0; i < n; i++) { 
     f2(n - 1); 
    } 
} 

Die Lösung Ich kam zu O (2^n), aber die richtige Antwort wird als O (n!) Angegeben und ich verstehe nicht, wie das möglich ist und wäre wirklich dankbar, wenn jemand es erklären könnte mich.

Answer 1

for (i = 0; i < n; i++) { 
     f2(n - 1); 
    } 

so äußere Schleife läuft n-mal, und rekursiv aufruft (n-mal) eine innere Schleife, die n-1-mal ausgeführt wird, bis 1.

So erreichen sie läuft n! mal alles in Ordnung.

Answer 2

Betrachten unterhalb Funktion

void fact(int n) { 
    int i; 
    if (n == 1) { 
     return; 
    } 
    for(int i=0; i<n; i++) { 
    fact(n-1); 
    } 
} 

Angenommen n=2;

die Funktion wird

void fact(int n) { 

    fact(1); 
    fact(1); 

} 

Scheint, wie Zeitkomplexität exponentiell ist.

Es sei nun angenommen n=4

void fact(int n) { 

    fact(3); 
    // -- this leads to fact(2) fact(2) fact(2) 
    // -- which leads to fact(1) fact(1) fact(1) fact(1) fact(1) fact1) 

    fact(3); 
    fact(3); 
    fact(3); 
} 

schließlich endet es mit O(n!)