Komplexitet och rekursiva funktioner

> LeekScript handledning

Varning: Den här artikeln är matematiskt intensiv (åtminstone för denna wiki). Använd inte utan medicinsk rådgivning.

Mer allvarligt: här ska jag försöka prata om Optimering av rekursiva funktioner (The_Recursion). Den här artikeln är mer för personer som är intresserade av funktionell programmering och programmeringsteori.

Det är inte alltid lätt, när man skriver en rekursiv funktion, att veta hur många samtal vi kommer att ringa innan vi kommer fram till resultatet. Eller till och med om vi kommer fram till resultatet, ibland. Handledningen om La_Récursivité ger sätt att optimera rekursiva funktioner, men studerar inte komplexitet eller korrigering; Jag ska därför här illustrera med exempel några metoder för att hitta rätt.

Denna lista med exempel är inte avsedd att vara uttömmande, det kommer att vara nödvändigt för var och en av dina algoritmer att undersöka exakt de operationer som utförs.

Sedan är det upp till dig att kopiera dessa idéer för dina personliga algoritmer, och om du hittar andra exempel värda att nämna, förklara dem här!

Första exemplen

Vissa enkla rekursiva funktioner har en komplexitet som är lätt att studera. Detta är fallet med det första exemplet på handledningen om rekursion:

funktion summaN(n) { if (n === 0) { return 0; } else { return n + summaN(n - 1); } }

Här är det ganska enkelt: vi kan lätt se att om vi ger ett heltal n (positivt!) till denna funktion, kommer den att lägga till n till summan från 0 till n-1, som den beräknar genom att kalla sig själv-jämn. Så vi kommer att göra n + (n-1 + ... + (0)...), vilket gör n tillägg och n funktionsanrop, dvs en komplexitet av O( n).

Men om vi anger ett negativt heltal som indata kommer denna funktion att orsaka ett stackspill: den kommer att lägga till negativa tal utan att någonsin nå 0. På samma sätt, om vi ger ett icke-heltal, kommer vi aldrig att nå 0 genom att subtrahera 1 flera gånger . Så var uppmärksam på '''korrigeringen''' av dina rekursiva funktioner: om du inte har förutsett alla fall eller om du använder dem med en ingång som inte motsvarar vad du hade i åtanke när du kodade den, kan du ha obehagliga överraskningar.

Optimeringshandledningen ger ett exempel på en O(2^n)-komplexitetsfunktion:

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

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

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

//Vi duplicerar sedan listan med kombinationer: vi behåller de vi hade, och vi lägger till samma med det första elementet av list_items for(var i=0; i P(n) = 2*P(n-1). Eftersom vi också har P(1) = 2, får vi formeln P(n) = 2 * ... * 2 = 2^n, därav (vid minst) exponentiell komplexitet. Vi kan sedan visa att denna funktion har en exponentiell komplexitet (och inte större): varje anrop till funktionen skapar en array av storleken n-1 med subArray (kostnad: O(n )), trycker sedan m med m storleken på den partiella kombinationsmatrisen, dvs. 2^(n-1) (kostnad: K * 2^(n-1) med K pushen cost), som krossar kostnaden för subArrayen, och därmed leder till en komplexitet som bestäms av antalet P(n) av pushar som utförs.

Det är denna idé som jag kommer att utveckla här: skaffa en återkommande formel och försöka härleda en formel för att öka antalet anrop, för att slutligen härleda komplexiteten genom att studera vad funktionen gör förutom sina anrop rekursiva. Jag ska inte prata så mycket om korrigering längre (förutom i slutet), men håll tanken i åtanke...

I det följande kommer C(n) att beteckna kostnaden för den studerade funktionen.

Enkla återkommande: C(n) = f(C(n-1))

Ordet "enkelt" här betyder inte att komplexen