Ich habe morgen eine Informatik-Halbzeit und brauche Hilfe bei der Bestimmung der Komplexität dieser rekursiven Funktionen. 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 mir beim 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);
}
recursion
big-o
complexity-theory
Michael_19
quelle
quelle
Antworten:
Die zeitliche Komplexität in Big O-Notation für jede Funktion ist in numerischer Reihenfolge:
O(n)
wird sie häufig als linear bezeichnet .O(n)
. (Wird tatsächlich als n / 5-fache Ordnung bezeichnet. Und O (n / 5) = O (n)).O(log(n))
(Basis 5), oft logarithmisch und meistens Big O-Notation und Komplexitätsanalyse, Basis 2.O(2^n)
, oder exponentiell , da jeder Funktionsaufruf selbst nennt zweimal es sei denn , es rekursiv wurde n - mal.Was die letzte Funktion betrifft, so nimmt die for-Schleife n / 2, da wir um 2 zunehmen, und die Rekursion n-5, und da die for-Schleife rekursiv aufgerufen wird, liegt die Zeitkomplexität in (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n, aufgrund des asymptotischen Verhaltens und der Überlegungen zum Worst-Case-Szenario oder der Obergrenze, die das große O anstrebt, interessieren wir uns nur für den größten Begriff
O(n^2)
.Viel Glück auf deiner Halbzeit;)
quelle
n/2
Iterationen derfor
Schleife führt, warum würde das Dekrementieren um 5 nicht zun/5
rekursiven Aufrufen führen? Dies würde immer noch zuO(n^2)
einer intuitiveren Erklärung führen. Warum Subtraktion und Division mischen, wenn sie unbedingt dasselbe tun müssen?n/5
nicht seinn-5
. Und letztendlich läuft das Ganze darauf hinausO(N^2)
.Für den Fall, wo
n <= 0
,T(n) = O(1)
. Daher hängt die zeitliche Komplexität davon ab, wannn >= 0
.Wir werden den Fall
n >= 0
im folgenden Teil betrachten.1.
wo a eine Konstante ist.
Durch Induktion:
wobei a, b eine Konstante sind.
2.
wo a eine Konstante ist
Durch Induktion:
wobei a, b eine Konstante sind und k <= 0
3.
wo a eine Konstante ist
Durch Induktion:
wobei a, b eine Konstante sind
4.
wo a eine Konstante ist
Durch Induktion:
wobei a, b eine Konstante sind.
5.
wobei n eine Konstante ist
Schreiben Sie neu,
n = 5q + r
wobei q und r eine ganze Zahl sind und r = 0, 1, 2, 3, 4Wir haben
q = (n - r) / 5
, und da r <5 ist, können wir es als Konstante betrachten, alsoq = O(n)
Durch Induktion:
Da r <4 ist, können wir eine Konstante b finden, so dass
b >= T(r)
quelle
Eine der besten Möglichkeiten, die Komplexität des rekursiven Algorithmus zu approximieren, ist das Zeichnen des Rekursionsbaums. Sobald Sie den rekursiven Baum haben:
n
und Anzahl der Blattknoten,1
so dass die Komplexität sein wirdn*1 = n
Die zweite Funktion hat wieder die Länge
n/5
und Anzahl der Blattknoten,1
so dass die Komplexität zunimmtn/5 * 1 = n/5
. Es sollte angenähert werden ann
Für die dritte Funktion wird, da
n
bei jedem rekursiven Aufruf durch 5 geteilt wird, die Länge des rekursiven Baumslog(n)(base 5)
und die Anzahl der Blattknoten wieder 1 sein, so dass die Komplexität sein wirdlog(n)(base 5) * 1 = log(n)(base 5)
Für die vierte Funktion ist, da jeder Knoten zwei untergeordnete Knoten hat, die Anzahl der Blattknoten gleich
(2^n)
und die Länge des rekursiven Baumsn
so komplex(2^n) * n
. Aber dan
es vor unbedeutend ist(2^n)
, kann es ignoriert werden und Komplexität kann nur als solche bezeichnet werden(2^n)
.Für die fünfte Funktion gibt es zwei Elemente, die die Komplexität einführen. Komplexität, die durch die rekursive Natur der Funktion eingeführt wird, und Komplexität, die durch die
for
Schleife in jeder Funktion eingeführt wird. Bei der obigen Berechnung wird die Komplexität, die durch die rekursive Natur der Funktion eingeführt wird,~ n
und die Komplexität aufgrund der for-Schleife seinn
. Gesamtkomplexität wird seinn*n
.Hinweis: Dies ist eine schnelle und schmutzige Methode zur Berechnung der Komplexität (nichts offizielles!). Würde gerne Feedback dazu hören. Vielen Dank.
quelle
2^n
die Höhe des Baumes seinn
, nichtlog n
. Die Höhe wäre nur,log n
wennn
die Gesamtzahl der Knoten im Baum dargestellt würde. Aber das tut es nicht.Wir können es mathematisch beweisen, was mir in den obigen Antworten gefehlt hat.
Es kann Ihnen dramatisch helfen, zu verstehen, wie eine Methode berechnet wird. Ich empfehle, es von oben nach unten zu lesen, um zu verstehen, wie es geht:
T(n) = T(n-1) + 1
Dies bedeutet, dass die Zeit, die für das Beenden der Methode benötigt wird, der gleichen Methode entspricht, jedoch mit n-1,T(n-1)
und wir fügen jetzt hinzu,+ 1
da es die Zeit ist, die benötigt wird, um die allgemeinen Operationen abzuschließen (außerT(n-1)
). Nun werden wir Folgendes feststellenT(n-1)
:T(n-1) = T(n-1-1) + 1
. Es sieht so aus, als könnten wir jetzt eine Funktion bilden, die uns eine Art Wiederholung geben kann, damit wir sie vollständig verstehen können. Wir werden die rechte SeiteT(n-1) = ...
stattT(n-1)
innerhalb der Methode platzieren,T(n) = ...
die uns geben wird:T(n) = T(n-1-1) + 1 + 1
was istT(n) = T(n-2) + 2
oder mit anderen Worten, wir müssen unsere fehlenden findenk
:T(n) = T(n-k) + k
. Der nächste Schritt besteht darin, zun-k
behaupten,n-k = 1
dass am Ende der Rekursion genau O (1) benötigt wird, wennn<=0
. Aus dieser einfachen Gleichung wissen wir das jetztk = n - 1
. Lassen Sie unsk
in unsere endgültige Methode setzen:T(n) = T(n-k) + k
was uns geben wird:T(n) = 1 + n - 1
was genaun
oder istO(n)
.O(n)
.T(n) = T(n/5) + 1
Nach wie vor entspricht die Zeit bis zum Abschluss dieser Methode der Zeit derselben Methode, ann/5
die sie jedoch gebunden istT(n/5)
. Lassen Sie unsT(n/5)
wie in 1 finden:T(n/5) = T(n/5/5) + 1
was istT(n/5) = T(n/5^2) + 1
. Lassen Sie uns Platz imT(n/5)
InnerenT(n)
für die endgültige Berechnung:T(n) = T(n/5^k) + k
. Wieder wie zuvor,n/5^k = 1
wasn = 5^k
genau so ist, als würde man fragen, was in Potenz von 5 uns n geben wird, lautet die Antwortlog5n = k
(Protokoll von Basis 5). Lassen Sie uns unsere ErgebnisseT(n) = T(n/5^k) + k
wie folgt einordnen:T(n) = 1 + logn
Welches istO(logn)
T(n) = 2T(n-1) + 1
Was wir hier haben, ist im Grunde das gleiche wie zuvor, aber dieses Mal rufen wir die Methode 2 Mal rekursiv auf, also multiplizieren wir sie mit 2. Lassen Sie uns herausfinden,T(n-1) = 2T(n-1-1) + 1
welche istT(n-1) = 2T(n-2) + 1
. Unser nächster Ort wie zuvor, wir setzen unsere Erkenntnis:T(n) = 2(2T(n-2)) + 1 + 1
das istT(n) = 2^2T(n-2) + 2
das gibt unsT(n) = 2^kT(n-k) + k
. Lassen Sie uns herausfindenk
, wasn-k = 1
das istk = n - 1
. Lassen Sie unsk
wie folgt platzieren: DasT(n) = 2^(n-1) + n - 1
ist ungefährO(2^n)
T(n) = T(n-5) + n + 1
Es ist fast dasselbe wie 4, aber jetzt fügen wir hinzu,n
weil wir einefor
Schleife haben. Lassen Sie uns herausfinden,T(n-5) = T(n-5-5) + n + 1
was istT(n-5) = T(n - 2*5) + n + 1
. Lassen Sie es uns platzieren:T(n) = T(n-2*5) + n + n + 1 + 1)
was istT(n) = T(n-2*5) + 2n + 2)
und für das k:T(n) = T(n-k*5) + kn + k)
wieder:n-5k = 1
was istn = 5k + 1
das ist ungefährn = k
. Dies wird uns geben:T(n) = T(0) + n^2 + n
was ungefähr istO(n^2)
.Ich empfehle jetzt, den Rest der Antworten zu lesen, um eine bessere Perspektive zu erhalten. Viel Glück beim Gewinnen dieser großen O's :)
quelle
Der Schlüssel hier ist die Visualisierung des Anrufbaums. Sobald dies erledigt ist, ist die Komplexität:
Der letztere Term kann genauso berechnet werden wie für eine normale iterative Funktion.
Stattdessen werden die Gesamtknoten eines vollständigen Baums als berechnet
Dabei ist C die Anzahl der untergeordneten Elemente jedes Knotens und L die Anzahl der Ebenen des Baums (einschließlich Wurzel).
Es ist einfach, den Baum zu visualisieren. Beginnen Sie mit dem ersten Aufruf (Stammknoten) und zeichnen Sie eine Anzahl von untergeordneten Elementen, 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.
Also, in den obigen Beispielen:
quelle