Der Schlüssel dazu ist die Visualisierung des Anrufbaums. Sobald dies geschehen ist, ist die Komplexität:
nodes of the call tree * complexity of other code in the function
Der letztere Term kann auf die gleiche Weise berechnet werden wie bei einer normalen iterativen Funktion.
Stattdessen werden die Gesamtknoten eines vollständigen Baums wie folgt berechnet
C^L - 1
------- , when C>1
/ C - 1
/
# of nodes =
\
\
L , when C=1 (this is special case of a single branch tree)
Dabei steht C für die Anzahl der Kinder jedes Knotens und L für die Anzahl der Ebenen des Baums (einschließlich der Wurzel).
Es ist einfach, sich den Baum vorzustellen. Beginnen Sie mit dem ersten Aufruf (Wurzelknoten) und zeichnen Sie dann eine Anzahl von Kindern ein, die der Anzahl der rekursiven Aufrufe in der Funktion entspricht. Es ist auch nützlich, den an den Unteraufruf übergebenen Parameter als "Wert des Knotens" zu schreiben.
Hier also die Ergebnisse für die obigen Beispiele:
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
Denken Sie zunächst an den Anrufbaum:
n level 1
n-1 level 2
n-2 level 3
n-3 level 4
... ~ n levels -> L = n
Hier ist die Anzahl der Kinder pro Knoten C = 1 und die Anzahl der Ebenen L = n+1. Die Komplexität des Rests der Funktion ist O(1). Daher ist die Gesamtkomplexität L * O(1) = (n+1) * O(1) = O(n)
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
Der Anrufbaum lautet hier:
n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5
Wiederum ist C = 1, aber L = n/5. Die Komplexität des Rests der Funktion ist O(1). Daher ist die Gesamtkomplexität L * O(1) = (n/5) * O(1) = O(n)
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
Der Anrufbaum lautet:
n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)
Folglich ist C = 1, L = log(n). Die Komplexität des Rests der Funktion ist O(1). Daher ist die Gesamtkomplexität L * O(1) = log5(n) * O(1) = O(log(n))
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
Hier ist der Aufrufbaum komplexer:
n level 1
n-1 n-1 level 2
n-2 n-2 n-2 n-2 ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3 ...
... ~ n levels -> L = n
Hier ist die Anzahl der Kinder pro Knoten C = 2, während L = n. Die Komplexität der restlichen Funktion ist O(1). Diesmal verwenden wir die vollständige Formel für die Anzahl der Knoten im Aufrufbaum, da C > 1 ist. Daher ist die Gesamtkomplexität (C^L-1)/(C-1) * O(1) = (2^n - 1) * O(1) = O(2^n) .
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
Auch hier ist der Anrufbaum:
n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5
Hier ist C = 1, L = n/5. Die Komplexität des Rests der Funktion ist O(n). Daher ist die Gesamtkomplexität L * O(1) = (n/5) * O(n) = O(n^2)
