Komplexität und rekursive Funktionen

> LeekScript-Tutorial

Warnung: Dieser Artikel ist mathematisch intensiv (zumindest für dieses Wiki). Nicht ohne ärztlichen Rat verwenden.

Ernsthafter: Hier werde ich versuchen, über die Optimierung rekursiver Funktionen (The_Recursion) zu sprechen. Dieser Artikel richtet sich eher an Personen, die sich für funktionale Programmierung und Programmiertheorie interessieren.

Beim Schreiben einer rekursiven Funktion ist es nicht immer einfach zu wissen, wie viele Aufrufe wir machen werden, bevor wir das Ergebnis erhalten. Oder auch wenn wir manchmal zum Ergebnis kommen. Das Tutorial zu La_Récursivité zeigt Wege auf, rekursive Funktionen zu optimieren, untersucht aber nicht die Komplexität oder Korrektur; Ich werde daher hier mit Beispielen einige Methoden veranschaulichen, um sich zurechtzufinden.

Diese Liste von Beispielen erhebt keinen Anspruch auf Vollständigkeit, es ist notwendig, dass jeder Ihrer Algorithmen die durchgeführten Operationen genau untersucht.

Dann liegt es an Ihnen, diese Ideen für Ihre persönlichen Algorithmen zu kopieren, und wenn Sie weitere erwähnenswerte Beispiele finden, erläutern Sie diese hier!

Erste Beispiele

Einige einfache rekursive Funktionen haben eine leicht zu studierende Komplexität. Dies ist beim ersten Beispiel des Tutorials zur Rekursion der Fall:

Funktion SummeN(n) { Wenn (n === 0) {Rückgabe 0; } Sonst {Rückgabe n + sumN(n - 1); } }

Hier ist es ganz einfach: Wir können leicht sehen, dass, wenn wir dieser Funktion eine ganze Zahl n (positiv!) geben, sie n zu der Summe von 0 bis n-1 addiert, die sie berechnet, indem sie sich selbst aufruft – gerade. Also machen wir n + (n-1 + ... + (0)...), was n Additionen und n Funktionsaufrufe macht, also eine Komplexität von O( n).

Wenn wir jedoch eine negative Ganzzahl als Eingabe angeben, verursacht diese Funktion einen Stapelüberlauf: Sie addiert negative Zahlen, ohne jemals 0 zu erreichen. Wenn wir eine nicht ganzzahlige Zahl eingeben, werden wir in ähnlicher Weise niemals 0 erreichen, indem wir 1 mehrmals subtrahieren . Achten Sie also auf die '''Korrektur''' Ihrer rekursiven Funktionen: Wenn Sie nicht alle Fälle vorhergesehen haben oder wenn Sie sie mit einer Eingabe verwenden, die nicht dem entspricht, was Sie beim Codieren im Sinn hatten, könnten Sie es tun unangenehme Überraschungen.

Das Optimierungs-Tutorial gibt ein Beispiel für eine O(2^n)-Komplexitätsfunktion:

Funktion getAllCombos(list_items){ var nb_items = count(list_items);

if(nb_items == 1) { return [[], list_items]; }

var sub_list = subArray(list_items, 1, nb_items - 1); var partial_combos_list = getAllCombos(sub_list); // Rekursiver Aufruf var m = count(list_combos_partial);

// Wir duplizieren dann die Liste der Kombinationen: Wir behalten die, die wir hatten, und wir fügen dieselben mit dem ersten Element von liste_items hinzu for(var i=0; i P(n) = 2*P(n-1). Da wir auch P(1) = 2 haben, erhalten wir die Formel P(n) = 2 * ... * 2 = 2^n, also die (at mindestens) exponentielle Komplexität. Wir können dann zeigen, dass diese Funktion eine exponentielle Komplexität hat (und nicht größer): Jeder Aufruf der Funktion erzeugt ein Array der Größe n-1 mit subArray (Kosten: O(n )), dann pusht m mit m die Größe des partiellen Combo-Arrays, also 2^(n-1) (Kosten: K * 2^(n-1) mit K der Push cost), was die Kosten des subArrays zunichte macht und somit zu einer Komplexität führt, die durch die Anzahl P(n) der durchgeführten Pushs bestimmt wird.

Es ist diese Idee, die ich hier entwickeln werde: Erhalten Sie eine Wiederholungsformel und versuchen Sie, eine Formel abzuleiten, um die Anzahl der Aufrufe zu erhöhen, um schließlich die Komplexität abzuleiten, indem Sie untersuchen, was die Funktion zusätzlich zu ihren rekursiven Aufrufen tut. Ich werde nicht mehr so viel über Korrektur sprechen (außer ganz am Ende), aber behalten Sie den Begriff im Hinterkopf ...

Im Folgenden bezeichnet C(n) die Kosten der untersuchten Funktion.

Einfache Wiederholungen: C(n) = f(C(n-1))

Das Wort „einfach“ bedeutet hier nicht, dass das Komplexi