Wie bestimme ich die Laufzeit einer doppelten rekursiven Funktion?

15

Wie würde man bei einer willkürlich doppelt rekursiven Funktion ihre Laufzeit berechnen?

Zum Beispiel (im Pseudocode):

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

Oder so ähnlich.

Mit welchen Methoden könnte oder sollte man so etwas bestimmen?

if_zero_equals_one
quelle
2
Ist das Hausaufgabe?
Bernard
5
Nein, es ist Sommer und ich lerne gerne. Ich schätze, ich komme voran, anstatt mein Gehirn zu Brei werden zu lassen.
if_zero_equals_one
11
Okay, verstanden. Für diejenigen, die abstimmen, dies in Stack Overflow zu migrieren: Dies ist hier thematisch und nicht thematisch in Stack Overflow. Programmers.SE ist für konzeptionelle Whiteboard-Fragen gedacht. Der Stapelüberlauf ist für die Implementierung gedacht und stellt Fragen, während ich programmiere.
3
Danke, das ist der Grund, warum ich es hier gemacht habe. Außerdem ist es besser zu wissen, wie man fischt, als einen Fisch zu erhalten.
if_zero_equals_one
1
In diesem speziellen Fall handelt es sich im Allgemeinen immer noch um eine unendliche Rekursion, da b (a (0)) unendlich viele andere b (a (0)) - Terme aufruft. Es wäre anders gewesen, wenn es eine mathematische Formel wäre. Wäre Ihr Setup anders gewesen, hätte es anders geklappt. Genau wie in der Mathematik haben in cs einige Probleme eine Lösung, manche nicht, manche haben eine einfache, manche nicht. Es gibt viele gegenseitig rekursive Fälle, in denen die Lösung existiert. Manchmal muss man ein Trampolinmuster verwenden, um einen Stapel nicht zu sprengen.
Job

Antworten:

11

Sie ändern immer wieder Ihre Funktion. Aber suchen Sie sich weiterhin solche aus, die für immer ohne Konvertierung auskommen.

Rekursion wird kompliziert, schnell. Der erste Schritt zur Analyse einer vorgeschlagenen doppelt rekursiven Funktion besteht darin, sie anhand einiger Beispielwerte zu verfolgen, um zu sehen, was sie bewirkt. Wenn Ihre Berechnung in eine Endlosschleife gerät, ist die Funktion nicht genau definiert. Wenn Ihre Berechnung in eine Spirale gerät, die immer größere Zahlen enthält (was sehr leicht vorkommt), ist sie wahrscheinlich nicht genau definiert.

Wenn Sie eine Antwort finden, versuchen Sie, ein Muster oder eine Wiederholungsbeziehung zwischen den Antworten zu finden. Sobald Sie das haben, können Sie versuchen, seine Laufzeit herauszufinden. Das herauszufinden kann sehr, sehr kompliziert sein, aber wir haben Ergebnisse wie den Hauptsatz , mit denen wir die Antwort in vielen Fällen herausfinden können.

Beachten Sie, dass es auch bei einer einzelnen Rekursion leicht ist, Funktionen zu finden, deren Laufzeit wir nicht berechnen können. Betrachten Sie zum Beispiel Folgendes:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

Es ist derzeit nicht bekannt, ob diese Funktion immer genau definiert ist, geschweige denn, wie lange sie ausgeführt wird.

btilly
quelle
5

Die Laufzeit dieses bestimmten Funktionspaares ist unendlich, da keine der beiden Funktionen zurückkehrt, ohne die andere aufzurufen. Der Rückgabewert aist immer abhängig von dem Rückgabewert eines Anruf zu bdem immer ruft a... und das ist , was als bekannt ist unendliche Rekursion .

Jimreed
quelle
Ich suche hier nicht nach den speziellen Funktionen. Ich suche nach einem allgemeinen Weg, um die Laufzeit von rekursiven Funktionen zu finden, die sich gegenseitig aufrufen.
if_zero_equals_one
1
Ich bin mir nicht sicher, ob es im allgemeinen Fall eine Lösung gibt. Damit Big-O Sinn macht, muss man wissen, ob der Algorithmus jemals anhält. Es gibt einige rekursive Algorithmen, bei denen Sie die Berechnung ausführen müssen, bevor Sie wissen, wie lange es dauern wird (z. B. Ermitteln, ob ein Punkt zum Mandlebrot-Satz gehört oder nicht).
5.
Nicht immer, aruft nur an, bwenn die übergebene Nummer> = 0 ist. Aber ja, es gibt eine Endlosschleife.
btilly
1
@btilly Das Beispiel wurde geändert, nachdem ich meine Antwort gepostet habe.
5.
1
@jimreed: Und es wurde wieder geändert. Ich würde meinen Kommentar löschen, wenn ich könnte.
btilly
4

Die naheliegende Methode besteht darin, die Funktion auszuführen und zu messen, wie lange es dauert. Hier erfahren Sie jedoch nur, wie lange eine bestimmte Eingabe dauert. Und wenn Sie vorher nicht wissen, dass die Funktion beendet wird, gibt es keine mechanische Möglichkeit, um herauszufinden, ob die Funktion beendet wird - das ist das Problem , das zum Stillstand kommt , , und es ist nicht zu entscheiden.

Das Ermitteln der Laufzeit einer Funktion ist nach dem Satz von Rice in ähnlicher Weise unentscheidbar . Tatsächlich zeigt der Satz von Rice, dass sogar entschieden wird, ob eine Funktion ausgeführt wirdO(f(n)) Zeit treffen ist.

Das Beste, was Sie im Allgemeinen tun können, ist, Ihre menschliche Intelligenz (die unseres Wissens nicht an die Grenzen von Turing-Maschinen gebunden ist) zu nutzen und zu versuchen, ein Muster zu erkennen oder ein solches zu erfinden. Eine typische Methode zum Analysieren der Laufzeit einer Funktion besteht darin, die rekursive Definition der Funktion in eine rekursive Gleichung für ihre Laufzeit umzuwandeln (oder einen Satz von Gleichungen für wechselseitig rekursive Funktionen):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

Was nun? Sie haben jetzt ein mathematisches Problem: Sie müssen diese Funktionsgleichungen lösen. Ein Ansatz, der häufig funktioniert, besteht darin, diese Gleichungen für ganzzahlige Funktionen in Gleichungen für analytische Funktionen umzuwandeln und diese mithilfe von Kalkül zu lösen, die Funktionen zu interpretieren T_aund Funktionen T_bzu erzeugen .

Zur Erzeugung von Funktionen und anderen diskreten mathematischen Themen empfehle ich das Buch Concrete Mathematics von Ronald Graham, Donald Knuth und Oren Patashnik.

Gilles 'SO - hör auf böse zu sein'
quelle
1

Wie andere betonten, kann die Analyse der Rekursion sehr schnell sehr schwierig werden. Hier ist ein weiteres Beispiel dafür: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences Es ist schwierig, eine Antwort und eine Laufzeit für diese zu berechnen. Dies liegt daran, dass diese gegenseitig rekursiven Funktionen eine "schwierige Form" haben.

Wie auch immer, schauen wir uns dieses einfache Beispiel an:

http://pramode.net/clojure/2010/05/08/clojure-trampoline/

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Beginnen wir mit dem Versuch, Folgendes zu berechnen funa(m), m > 0:

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

Die Laufzeit beträgt:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

Lassen Sie uns nun ein anderes, etwas komplizierteres Beispiel auswählen:

Inspiriert von http://planetmath.org/encyclopedia/MutualRecursion.html , was für sich genommen eine gute Lektüre ist, betrachten wir: "" Fibonacci-Zahlen können durch gegenseitige Rekursion interpretiert werden: F (0) = 1 und G (0) ) = 1 mit F (n + 1) = F (n) + G (n) und G (n + 1) = F (n).

Was ist die Laufzeit von F? Wir werden den anderen Weg gehen.
Nun, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Jetzt ist R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Es ist nicht schwer zu erkennen, dass R (F (m)) = F (m) - z. B. ist die Anzahl der Funktionsaufrufe, die zum Berechnen einer Fibonacci-Zahl am Index i erforderlich sind, gleich dem Wert einer Fibonacci-Zahl am Index i. Dies setzt voraus, dass das Addieren von zwei Zahlen viel schneller ist als ein Funktionsaufruf. Wenn dies nicht der Fall wäre, dann wäre dies wahr: R (F (1)) = R (F (0)) + 1 + R (G (0)), und die Analyse davon wäre komplizierter gewesen, möglicherweise ohne eine einfache geschlossene Formlösung.

Die geschlossene Form der Fibonacci-Sequenz ist nicht unbedingt leicht neu zu erfinden, ganz zu schweigen von einigen komplizierteren Beispielen.

Job
quelle
0

Zunächst muss gezeigt werden, dass die von Ihnen definierten Funktionen enden und für welche Werte genau. In dem von Ihnen definierten Beispiel

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

bKündigt nur für an, y <= -5denn wenn Sie einen anderen Wert einstecken, haben Sie eine Laufzeit des Formulars b(a(y-1)). Wenn Sie etwas weiter expandieren, werden Sie feststellen, dass ein Term der Form b(a(y-1))schließlich zu dem Term b(1010)führt, der zu einem Term b(a(1009))führt, der wiederum zu dem Term führt b(1010). Dies bedeutet, dass Sie keinen Wert einfügen können a, der nicht erfüllt, x <= -4da Sie am Ende eine Endlosschleife haben, in der der zu berechnende Wert vom zu berechnenden Wert abhängt. Dieses Beispiel hat also im Wesentlichen eine konstante Laufzeit.

Die einfache Antwort lautet also, dass es keine allgemeine Methode zum Ermitteln der Laufzeit rekursiver Funktionen gibt, da es keine allgemeine Prozedur gibt, die bestimmt, ob eine rekursiv definierte Funktion beendet wird.

davidk01
quelle
-5

Laufzeit wie in Big-O?

Das ist ganz einfach: O (N) - vorausgesetzt, es liegt eine Beendigungsbedingung vor.

Rekursion ist nur eine Schleife, und eine einfache Schleife ist O (N), egal wie viele Dinge Sie in dieser Schleife tun (und das Aufrufen einer anderen Methode ist nur ein weiterer Schritt in der Schleife).

Interessant wird es, wenn Sie eine Schleife innerhalb einer oder mehrerer der rekursiven Methoden haben. In diesem Fall erhalten Sie eine Art exponentielle Leistung (multipliziert mit O (N) bei jedem Durchgang durch die Methode).

Anon
quelle
2
Sie bestimmen die Big-O-Leistung, indem Sie die höchste Ordnung einer aufgerufenen Methode mit der Ordnung der aufrufenden Methode multiplizieren. Sobald Sie jedoch über exponentielle und faktorielle Leistung sprechen, können Sie die polynomielle Leistung ignorieren. Ich glaube, dass das Gleiche gilt, wenn man Exponential und Fakultät vergleicht: Fakultät gewinnt. Ich musste noch nie ein System analysieren, das sowohl exponentiell als auch faktoriell war.
Anon
5
Das ist falsch. Die rekursive Form der n - ten Fibonacci - Zahl zu berechnen und quicksort sind O(2^n)und O(n*log(n))jeweils.
unpythonic
1
Ohne einen ausgefallenen Beweis zu erbringen, möchte ich Sie an amazon.com/Introduction-Algorithms-Second-Thomas-Cormen/dp/… weiterleiten und versuchen, einen Blick auf diese SE-Site zu werfen : cstheory.stackexchange.com .
Bryan Harrington
4
Warum haben die Leute diese schrecklich falsche Antwort gewählt? Das Aufrufen einer Methode benötigt Zeit, die proportional zu der Zeit ist, die diese Methode benötigt. In diesem Fall Methode aAnrufe bund bAnrufe , aso dass Sie können nicht einfach davon ausgehen , dass jede Methode Zeit in Anspruch nimmt O(1).
btilly
2
@Anon - Das Poster forderte eine willkürlich doppelt rekursive Funktion, nicht nur die oben gezeigte. Ich habe zwei Beispiele für einfache Rekursionen angeführt, die nicht zu Ihrer Erklärung passen. Es ist trivial, die alten Standards in eine "doppelt rekursive" Form umzuwandeln, eine, die exponentiell war (passend zu Ihrer Einschränkung) und eine, die nicht (nicht abgedeckt) ist.
unpythonic