Wie kann ich die zeitliche Komplexität eines rekursiven Algorithmus berechnen?Zeitkomplexität eines rekursiven Algorithmus
int pow1(int x,int n) {
if(n==0){
return 1;
}
else{
return x * pow1(x, n-1);
}
}
int pow2(int x,int n) {
if(n==0){
return 1;
}
else if(n&1){
int p = pow2(x, (n-1)/2)
return x * p * p;
}
else {
int p = pow2(x, n/2)
return p * p;
}
}
Analyse rekursive Funktionen (oder sogar sie zu bewerten) ist eine nicht triviale Aufgabe. A (meiner Meinung nach) gute Einführung in Don Knuths Concrete Mathematics finden.
Lassen Sie uns diese Beispiele jetzt analysieren:
Wir definieren eine Funktion, die uns die Zeit gibt, die eine Funktion benötigt. Nehmen wir an, t(n) bezeichnet die Zeit, die von pow(x,n) benötigt wird, d.h. eine Funktion von n.
Dann können wir schließen, dass t(0)=c, denn wenn wir pow(x,0) nennen, müssen wir prüfen, ob (n==0) und dann 1 zurückzukehren, die in konstanter Zeit durchgeführt werden kann (daher die Konstante c).
Jetzt betrachten wir den anderen Fall: n>0. Hier erhalten wir t(n) = d + t(n-1). Das liegt daran, dass wir erneut n==1 überprüfen, berechnen und daher das Ergebnis mit x multiplizieren müssen.Das Prüfen und Multiplizieren kann in konstanter Zeit erfolgen (Konstante d), die rekursive Berechnung von pow benötigt t(n-1).
Jetzt können wir "erweitern" der Begriff t(n):
t(n) =
d + t(n-1) =
d + (d + t(n-2)) =
d + d + t(n-2) =
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c
Also, wie lange dauert es, bis wir t(1) erreichen? Da wir bei t(n) beginnen und wir in jedem Schritt 1 subtrahieren, benötigen wir n-1 Schritte, um t(n-(n-1)) = t(1) zu erreichen. Das bedeutet andererseits, dass wir n-1 mal die Konstante d erhalten, und t(1) wird zu c ausgewertet. So
erhalten wir:
t(n) =
...
d + d + d + ... + c =
(n-1) * d + c
So erhalten wir, dass t(n)=(n-1) * d + c das Element von O (n) ist.
pow2 kann mit Masters theorem durchgeführt werden. Da wir davon ausgehen können, dass Zeitfunktionen für Algorithmen monoton steigend sind. So, jetzt haben wir die Zeit t(n) benötigt für die Berechnung von pow2(x,n):
t(0) = c (since constant time needed for computation of pow(x,0))
für n>0 bekommen wir
/t((n-1)/2) + d if n is odd (d is constant cost)
t(n) = <
\ t(n/2) + d if n is even (d is constant cost)
Die oben kann "vereinfachte" zu:
t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)
So wir Erhalte t(n) <= t(n/2) + d, was mit dem Masters Theorem zu t(n) = O(log n) gelöst werden kann (siehe Abschnitt Anwendung zu Popul ar Algorithmen im Wikipedia-Link, Beispiel "Binäre Suche").
Es kann ein bisschen kompliziert sein, aber ich denke, der üblicher Weg ist Master's theorem zu verwenden.
Complexity beiden Funktionen ignorieren Rekursion O (1)
Für den ersten Algorithmus POW1 (x, n) ist die Komplexität O (n), weil die Tiefe der Rekursion mit n linear korreliert.
Für die zweite Komplexität ist O (log n). Hier rekurven wir ungefähr log2 (n) mal. Wenn wir 2 auswerfen, erhalten wir log n.
Also ich vermute, dass Sie x auf die Macht n erhöhen. pow1 benötigt O (n).
Sie ändern nie den Wert von x, aber Sie nehmen 1 von n jedes Mal, bis es 1 erreicht (und Sie dann einfach zurück) Dies bedeutet, dass Sie einen rekursiven Aufruf n mal machen werden.
Beginnen wir einfach mit pow1, denn das ist das Einfachste.
Sie haben eine Funktion, bei der ein einzelner Lauf in O (1) ausgeführt wird. (Bedingungsprüfung, Rückgabe und Multiplikation sind konstante Zeit.)
Was Sie übrig haben, ist dann Ihre Rekursion. Was Sie tun müssen, ist zu analysieren, wie oft die Funktion sich selbst nennen würde. In Pow1 passiert es N-mal. N * O (1) = O (N).
Für pow2 ist es das gleiche Prinzip - ein einzelner Lauf der Funktion läuft in O (1). Allerdings nimmst du dieses Mal jedes Mal die Hälfte N. Das heißt, es wird log2 (N) mal laufen - effektiv einmal pro Bit. log2 (N) · O (1) = O (log (N)).
Etwas, das Ihnen helfen könnte, die Tatsache auszunutzen, dass Rekursion immer als Iteration ausgedrückt werden (nicht immer ganz einfach, aber es ist möglich. Wir können ausdrücken POW1 als
result = 1;
while(n != 0)
{
result = result*n;
n = n - 1;
}
Jetzt haben Sie einen iterativen Algorithmus statt, und man könnte es einfacher finden, es auf diese Weise zu analysieren.
Dieser Link liefert die genaue Antwort auf Ihr Problem. Hier ist die Quelle (http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf)
* Komplexität beider Funktionen ist O (1) * - Was? – kennytm
Es ist O (1) den rekursiven Aufruf zu ignorieren, könnte aber anders ausgedrückt werden. Der Punkt ist, dass die gesamte Komplexität nur von der Rekursionstiefe abhängt. – fgb