Wie findet man die Komplexität von rekursiven Algorithmen allgemein?

int factorial(int n) 
{ 
    if(n < 0) {return -1;} 
    if(n == 0) {return 1;} 
    return n*factorial(n-1); 
}

die Zeitkomplexität finde ich eine Rekursion erstellenWie findet man die Komplexität von rekursiven Algorithmen allgemein?

T(n) = T(n-1) + c = T(n-2) + 2c = ... = T(n-k) + kc => O(n) 
T(0) = 1;

Was die allgemeine Art und Weise ist der Raum Komplexität für diese Art von Algorithmen zu finden (wie Fibonacci)? Wir müssen eine Tiefe des Call-Stacks finden?

Quelle

2016-05-30 Anonymous

Nun werden Sie rekursiv es n-mal anrufen müssen, wird jeder Anruf einen eigenen Rahmen zuweisen auf Stapel mit lokalen Variablen, so Raumkomplexität ist die Reihenfolge von n. – Evk

Jeder Aufruf der Funktion "factorial" erzeugt einen Stack-Frame im Stack-Teil des Speichers für diesen Aufruf.Ein einzelner Stack-Frame enthält die in dieser Funktion definierten Variablen, die Parameter in der Funktion und die Rückgabeadresse. In diesem Fall kann diese Information für jeden Anruf in konstanter Zeit gespeichert werden. Da es eine lineare Anzahl von Aufrufen für diese Funktion geben wird, ist der Gesamtspeicher O (n). – Shubham

Der von einem rekursiven Algorithmus benötigte Speicherplatz kann durch drei Elemente angenähert werden. Raum

rekursive Stapel
Parameter zu speichern, benötigen Sie fließen in die Funktion
Ausgang einer Funktion

Im Beispiel eines faktoriellen. Rekursive Formel ist T(n) = T(n-1) + c. Beim Abrollen erhalten Sie T(n) = T(n-1) + T(n-2) + ... + n c. So erfordert rekursiver Stapel O(n) Speicherplatz.

Die Ausgabe einer Funktion wird n! sein, um eine Nummer n zu speichern, benötigen Sie Log (n) Bits. Um das Ergebnis zu speichern, benötigen Sie log(n!) = O(n log n) Speicherplatz.

Bei jedem Schritt Ihrer Rekursion müssen Sie 1 Parameter speichern (n). Sie müssen es n mal speichern, und jeder Parameter dauert log(n) Speicherplatz. Also insgesamt O(nlogn)

Sie endete also mit O(n) + O(nlogn) + O(nlogn) = O(nlogn). So viel Platz wird benötigt, um die Rekursion der Fakultät zu berechnen.

Doing diese Analyse können Sie finden, warum genau Schach-Programme, die alpa-Beta Beschneidung tun viel RAM erfordert richtig Positionen zu berechnen.

Quelle

2016-05-30 21:21:02

Ich habe deine Erklärung verstanden, aber warum alle anderen sagten, dass die Raumkomplexität O (n) ist? –

@ivan_petrushenko fragen Sie, wie viel Platz es braucht, um eine Zahl 'n!' Zu speichern. Wählen wir eine kleine Zahl "n", wie zB 5000. Werden sie sagen, dass es "O (1)" ist? –

Wahr. Für große Werte von "n" ist die Komplexität des Platzes nicht linear, und dasselbe gilt für die Zeitkomplexität (ich denke), weil dann ** das Multiplizieren von zwei sehr großen Zahlen nicht als konstante Zeitoperation ** in 'n * faktoriell returniert werden kann (n-1) '. Ich habe 'O (n)' geschrieben, weil ich angenommen habe, dass, da OP 'int' verwendet, es keine Zahlen speichern kann, die größer als' 19! 'Sind. – Shubham

Nach dem Schreiben Zeitkomplexität in Formen wie diese

T (n) = T (n - 1) + n

oder

T (n) = 2T (n/2) + nlogn

und so weiter.

Sie haben zwei Möglichkeiten:

1) wiederholt Substitutionsmethode verwenden, die in einigen Fällen einige mathematische Fähigkeiten ist braucht, weil Sie die Schritte, sollte bis T (1) oder T (0) und dann eine Summe berechnen.

oder

2) Mit den Master Satz, der wie eine Formel Master Theorem und arbeitet für viele praktische Fälle

Quelle

2016-05-31 03:38:24

Wie findet man die Komplexität von rekursiven Algorithmen allgemein?

Antwort

Verwandte Themen