Ich habe morgen eine Informatik-Mittelfrist und brauche Hilfe, um die Komplexität dieser rekursiven Funktionen zu bestimmen. Ich weiß, wie man einfache Fälle löst, aber ich versuche immer noch zu lernen, wie man diese schwierigeren Fälle löst. Dies waren nur einige der Beispielprobleme, die ich nicht herausfinden konnte. Jede Hilfe wäre sehr dankbar und würde in meinem Studium sehr helfen, Danke!
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
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);
}
}
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
Die Zeitkomplexität in Big O-Notation für jede Funktion ist in numerischer Reihenfolge:
O(n)
häufig als linear bezeichnet.O(n)
. (Wird tatsächlich n/5-mal aufgerufen. Und O(n/5) O(n)).O(log(n))
(base 5), oft logarithmisch und am häufigsten Big O genannt Die Notations- und Komplexitätsanalyse verwendet die Basis 2.O(2^n)
oder exponential, da jeder Funktionsaufruf sich selbst zweimal aufruft, es sei denn, er wurde n mal rekursiv ausgeführt.Was die letzte Funktion betrifft, nimmt die for-Schleife n/2, da wir um 2 erhöhen, und die Rekursion n-5, und da die for-Schleife rekursiv aufgerufen wird, ist die Zeitkomplexität in (n-5) * (n/2) = (2n-10) * n = 2n ^ 2- 10n, aufgrund von asymptotischem Verhalten und Worst-Case-Szenario-Überlegungen oder der von Big O angestrebten Obergrenze, interessiert uns nur der größte Term, also O(n^2)
.
Viel Glück auf deine Mitte;)
Für den Fall, dass n <= 0
, T(n) = O(1)
. Daher hängt die zeitliche Komplexität davon ab, wann n >= 0
.
Wir werden den Fall n >= 0
Im folgenden Teil betrachten.
1.
T(n) = a + T(n - 1)
wo ist eine Konstante.
Durch Induktion:
T(n) = n * a + T(0) = n * a + b = O(n)
wo a, b sind einige konstant.
2.
T(n) = a + T(n - 5)
wo ist eine Konstante
Durch Induktion:
T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)
wobei a, b eine Konstante sind und k <= 0
3.
T(n) = a + T(n / 5)
wo ist eine Konstante
Durch Induktion:
T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)
wo a, b sind einige konstant
4.
T(n) = a + 2 * T(n - 1)
wo ist eine Konstante
Durch Induktion:
T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2 ^ n
= a * 2^(n+1) - a + b * 2 ^ n
= (2 * a + b) * 2 ^ n - a
= O(2 ^ n)
wo a, b sind einige konstant.
5.
T(n) = n / 2 + T(n - 5)
Wir können durch Induktion beweisen, dass T(5k) >= T(5k - d)
mit d = 0, 1, 2, 3, 4
Schreiben Sie n = 5m - b
(M, b sind ganze Zahlen; b = 0, 1, 2, 3, 4), dann m = (n + b) / 5
:
T(n) = T(5m - b) <= T(5m)
(Um hier genauer zu sein, sollte eine neue Funktion T'(n)
so definiert werden, dass T'(5r - q) = T(5r)
wobei q = 0, 1, 2, 3, 4
. Wir kennen T(n) <= T'(n)
als bewiesen Wenn wir wissen, dass T'(n)
in O(f)
ist, was bedeutet, dass es eine Konstante a, b gibt, so dass T'(n) <= a * f(n) + b
, können wir diese T(n) <= a * f(n) + b
und daher T(n)
ist in O(f)
. Dieser Schritt ist nicht wirklich notwendig, aber es ist einfacher zu denken, wenn Sie sich nicht um den Rest kümmern müssen.)
Erweitern von T(5m)
:
T(5m) = 5m / 2 + T(5m - 5)
= (5m / 2 + 5 / 2) * m / 2 + T(0)
= O(m ^ 2) = O(n ^ 2)
Daher ist T(n)
O(n ^ 2)
.
Eine der besten Möglichkeiten, die Komplexität des rekursiven Algorithmus zu approximieren, ist das Zeichnen des Rekursionsbaums. Sobald Sie den rekursiven Baum haben:
Complexity = length of tree from root node to leaf node * number of leaf nodes
n
und die Nummer des Blattknotens 1
, Sodass die Komplexität n*1 = n
Ist.Die zweite Funktion hat wieder die Länge von n/5
Und die Anzahl der Blattknoten 1
, Sodass die Komplexität n/5 * 1 = n/5
Beträgt. Es sollte an n
angenähert werden
Für die dritte Funktion ist die Länge des rekursiven Baums log(n)(base 5)
und die Anzahl der Blattknoten wieder 1, da n
bei jedem rekursiven Aufruf durch 5 geteilt wird, also ist die Komplexität log(n)(base 5) * 1 = log(n)(base 5)
Für die vierte Funktion ist die Anzahl der Blattknoten gleich (2^n)
Und die Länge des rekursiven Baums ist n
, da jeder Knoten zwei untergeordnete Knoten hat. Die Komplexität ist also (2^n) * n
. Aber da n
vor (2^n)
Unbedeutend ist, kann es ignoriert werden und Komplexität kann nur als (2^n)
Bezeichnet werden.
Für die fünfte Funktion gibt es zwei Elemente, die die Komplexität einführen. Komplexität durch rekursive Art der Funktion und Komplexität durch for
Schleife in jeder Funktion eingeführt. Bei der obigen Berechnung ist die Komplexität, die durch die rekursive Natur der Funktion eingeführt wird, ~ n
Und die Komplexität aufgrund der for-Schleife n
. Die Gesamtkomplexität beträgt n*n
.
Hinweis: Dies ist eine schnelle und schmutzige Methode zur Berechnung der Komplexität (nichts offizielles!). Würde mich über Feedback freuen. Vielen Dank.