Kompleksitet og rekursive funktioner

> LeekScript vejledning

Advarsel: Denne artikel er matematisk intensiv (i hvert fald for denne wiki). Må ikke bruges uden lægehjælp.

Mere seriøst: her vil jeg prøve at tale om Optimering af rekursive funktioner (The_Recursion). Denne artikel er mere for folk, der er interesserede i funktionel programmering og programmeringsteori.

Det er ikke altid nemt, når man skriver en rekursiv funktion, at vide, hvor mange opkald vi vil foretage, før vi når frem til resultatet. Eller endda hvis vi vil nå frem til resultatet, nogle gange. Selvstudiet om La_Récursivité giver måder til at optimere rekursive funktioner, men studerer ikke kompleksitet eller korrektion; Jeg vil derfor her illustrere med eksempler nogle metoder til at finde rundt.

Denne liste over eksempler er ikke beregnet til at være udtømmende, det vil være nødvendigt for hver af dine algoritmer at undersøge præcist de udførte operationer.

Så er det op til dig at kopiere disse ideer til dine personlige algoritmer, og hvis du finder andre eksempler, der er værd at nævne, så forklar dem her!

Første eksempler

Nogle simple rekursive funktioner har en kompleksitet, der er nem at studere. Dette er tilfældet med det første eksempel på selvstudiet om rekursion:

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

Her er det ganske enkelt: Vi kan nemt se, at hvis vi giver et heltal n (positivt!) til denne funktion, vil den lægge n til summen fra 0 til n-1, som den beregner ved at kalde sig selv - lige. Så vi skal lave n + (n-1 + ... + (0)...), som laver n tilføjelser og n funktionskald, dvs. en kompleksitet på O( n).

Men hvis vi giver et negativt heltal som input, vil denne funktion forårsage et stak-overløb: den vil tilføje negative tal uden nogensinde at nå 0. På samme måde, hvis vi giver et ikke-heltal, vil vi aldrig nå 0 ved at trække 1 fra flere gange . Så vær opmærksom på '''korrektionen''' af dine rekursive funktioner: hvis du ikke har forudset alle tilfældene, eller hvis du bruger dem med et input, der ikke svarer til det, du havde i tankerne, da du kodede det, kunne du have ubehagelige overraskelser.

Optimeringsvejledningen giver et eksempel på en O(2^n) kompleksitetsfunktion:

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

if(nb_items == 1) { returner [[], liste_emner]; }

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

//Vi dublerer derefter listen over kombinationer: vi beholder dem, vi havde, og vi tilføjer de samme med det første element af liste_emner for(var i=0; i P(n) = 2*P(n-1). Da vi også har P(1) = 2, får vi formlen P(n) = 2 * ... * 2 = 2^n, deraf (at mindst) eksponentiel kompleksitet. Vi kan så vise, at denne funktion har en eksponentiel kompleksitet (og ikke større): hvert kald til funktionen skaber en matrix af størrelse n-1 med subArray (pris: O(n )), så skubber m med m størrelsen af den partielle kombinationsarray, dvs. 2^(n-1) (omkostninger: K * 2^(n-1) med K push cost), som knuser prisen på subArray'et og dermed fører til en kompleksitet bestemt af antallet P(n) af udførte push.

Det er denne idé, jeg vil udvikle her: få en gentagelsesformel og forsøge at udlede en formel for at øge antallet af kald, for til sidst at udlede kompleksiteten ved at studere, hvad funktionen gør ud over sine kald rekursive. Jeg vil ikke snakke så meget om korrektion længere (undtagen til allersidst), men husk tanken...

I det følgende vil C(n) angive prisen på den undersøgte funktion.

Simple gentagelser: C(n) = f(C(n-1))

Ordet "simpelt" her betyder ikke, at komplekserne