wake-up-neo.com

Komplexität für rekursive Funktionen bestimmen (Big O-Notation)

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);
}
recursionbig-ocomplexity-theory
224
Michael_19

Die Zeitkomplexität in Big O-Notation für jede Funktion ist in numerischer Reihenfolge:

  1. Die erste Funktion wird n-mal rekursiv aufgerufen, bevor der Basisfall erreicht wird. Daher wird die Funktion O(n) häufig als linear bezeichnet.
  2. Die zweite Funktion heißt jedes Mal n-5, also ziehen wir fünf von n ab, bevor wir die Funktion aufrufen, aber n-5 ist auch O(n). (Wird tatsächlich n/5-mal aufgerufen. Und O(n/5) O(n)).
  3. Diese Funktion ist log (n) zur Basis 5, für jedes Mal, wenn wir vor dem Aufrufen der Funktion durch 5 dividieren, damit ihre O(log(n)) (base 5), oft logarithmisch und am häufigsten Big O genannt Die Notations- und Komplexitätsanalyse verwendet die Basis 2.
  4. Im vierten Fall ist es O(2^n) oder exponential, da jeder Funktionsaufruf sich selbst zweimal aufruft, es sei denn, er wurde n mal rekursiv ausgeführt.

  5. 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;)

283
coder

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).

116
nhahtdh

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
  1. Die erste Funktion hat die Länge von n und die Nummer des Blattknotens 1, Sodass die Komplexität n*1 = n Ist.

  2. 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

  3. 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)

  4. 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.

  5. 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.

18
Shubham