Große O von rekursiven Methoden

Question

Ich habe Schwierigkeiten bei der Bestimmung der großen O von einfachen rekursiven Methoden. Ich kann mir nicht vorstellen, was passiert, wenn eine Methode mehrmals aufgerufen wird. Ich würde genauer über meine Bereiche der Verwirrung sprechen, aber im Moment versuche ich, einige hw Fragen zu beantworten, und anstatt zu mogeln, möchte ich, dass jeder, der auf diesen Beitrag antwortet, eine einfache rekursive Methode entwickelt und eine einfache Erklärung des großen O dieser Methode. (Vorzugsweise in Java ... eine Sprache, die ich lerne.)

Vielen Dank.

Answer 1

Sie können die Reihenfolge auch rekursiv definieren. Angenommen, Sie haben eine Funktion f. Um f (n) zu berechnen, werden k Schritte benötigt. Jetzt wollen Sie f (n + 1) berechnen. Nehmen wir an, f (n + 1) ruft f (n) einmal auf, dann nimmt f (n + 1) k + einige konstante Schritte an. Jeder Aufruf wird einige konstante zusätzliche Schritte benötigen, daher ist diese Methode O (n).

Schauen Sie sich jetzt ein anderes Beispiel an. Lassen Sie uns sagen Sie, indem die beiden bisherigen Ergebnisse Fibonacci naiver implementieren:

fib(n) = { return fib(n-1) + fib(n-2) } 

Jetzt können Sie sagen fib berechnen kann (n-2) und fib (n-1), die beide in etwa k Schritten. Um fib (n) zu berechnen, benötigen Sie k + k = 2 * k Schritte. Nehmen wir nun an, Sie wollen fib (n + 1) berechnen. Du brauchst also doppelt so viele Schritte wie bei fib (n-1). So scheint das zu sein O (2^N)

Zugegeben, das ist nicht sehr formell, aber hoffentlich auf diese Weise können Sie ein bisschen ein Gefühl bekommen.

Answer 2

Sie könnten sich auf den Hauptsatz zum Finden des großen O rekursiver Methoden beziehen. Hier ist der Wikipedia-Artikel: http://en.wikipedia.org/wiki/Master_theorem

Sie möchten an ein rekursives Problem wie ein Baum denken. Dann betrachte jede Ebene des Baumes und die Menge an Arbeit, die benötigt wird. Die Probleme werden im Allgemeinen in 3 Kategorien unterteilt: Wurzel schwer (erste Iteration >> Rest des Baumes), ausgewogen (jede Ebene hat die gleiche Menge an Arbeit), Blatt schwer (letzte Iteration >> Rest des Baumes). siehe

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

können Sie, dass jeder Aufruf von MergeSort ruft wiederum 2 weitere mergeSorts von 1/2 der Originallänge:

Taking Mergesort als Beispiel. Wir wissen, dass die Zusammenführungsprozedur Zeit benötigt, die proportional zur Anzahl der Werte ist, die zusammengeführt werden.

Die Rekursionsbeziehung ist dann T (n) = 2 · T (n/2) + O (n). Die zwei kommen von den 2 Anrufen und die n/2 von jedem Anruf haben nur die Hälfte der Anzahl der Elemente. Jedoch gibt es auf jeder Ebene die gleiche Anzahl von Elementen n, die zusammengeführt werden müssen, so dass die konstante Arbeit auf jeder Ebene O (n) ist.

Wir wissen, dass die Arbeit gleichmäßig verteilt ist (O (n) jede Tiefe) und der Baum log_2 (n) tief ist, also ist der große O der rekursiven Funktion O (n * log (n)).