Kompleksitet og rekursive funksjoner

> LeekScript-veiledning

Advarsel: Denne artikkelen er matematisk intensiv (i hvert fall for denne wikien). Ikke bruk uten medisinsk råd.

Mer seriøst: her skal jeg prøve å snakke om Optimalisering av rekursive funksjoner (The_Recursion). Denne artikkelen er mer for folk som er interessert i funksjonell programmering og programmeringsteori.

Det er ikke alltid lett, når du skriver en rekursiv funksjon, å vite hvor mange anrop vi skal ringe før vi kommer frem til resultatet. Eller selv om vi kommer frem til resultatet, noen ganger. Opplæringen om La_Récursivité gir måter å optimere rekursive funksjoner på, men studerer ikke kompleksitet eller korreksjon; Jeg vil derfor her illustrere med eksempler noen metoder for å finne frem.

Denne listen over eksempler er ikke ment å være uttømmende, det vil være nødvendig for hver av algoritmene dine å undersøke nøyaktig de utførte operasjonene.

Så er det opp til deg å kopiere disse ideene for dine personlige algoritmer, og hvis du finner andre eksempler verdt å nevne, forklar dem her!

Første eksempler

Noen enkle rekursive funksjoner har en kompleksitet som er lett å studere. Dette er tilfellet med det første eksemplet på opplæringen om rekursjon:

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

Her er det ganske enkelt: vi kan lett se at hvis vi gir et heltall n (positivt!) til denne funksjonen, vil den legge til n til summen fra 0 til n-1, som den beregner ved å kalle seg selv- jevn. Så vi skal gjøre n + (n-1 + ... + (0)...), som gjør n tillegg og n funksjonskall, dvs. en kompleksitet på O( n).

Men hvis vi gir et negativt heltall som input, vil denne funksjonen forårsake stabeloverflyt: den vil legge til negative tall uten noen gang å nå 0. På samme måte, hvis vi gir et ikke-heltall, vil vi aldri nå 0 ved å trekke fra 1 flere ganger . Så vær oppmerksom på '''korreksjonen''' av dine rekursive funksjoner: hvis du ikke har forutsett alle tilfellene eller hvis du bruker dem med en inngang som ikke samsvarer med det du hadde i tankene da du kodet den, kan du ha ubehagelige overraskelser.

Optimaliseringsveiledningen gir et eksempel på en kompleksitetsfunksjon O(2^n):

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

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

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 dupliserer deretter listen over kombinasjoner: vi beholder de vi hadde, og vi legger til de samme med det første elementet i liste_elementer for(var i=0; i P(n) = 2*P(n-1). Siden vi også har P(1) = 2, får vi formelen P(n) = 2 * ... * 2 = 2^n, derav (at minst) eksponentiell kompleksitet. Vi kan da vise at denne funksjonen har en eksponentiell kompleksitet (og ikke større): hvert kall til funksjonen lager en matrise av størrelse n-1 med subArray (kostnad: O(n )), så trykker m med m størrelsen på den delvise kombinasjonsmatrisen, dvs. 2^(n-1) (kostnad: K * 2^(n-1) med K push cost), som knuser kostnadene til subArrayen, og dermed fører til en kompleksitet som bestemmes av antall P(n) utførte push.

Det er denne ideen jeg skal utvikle her: få en gjentaksformel og prøve å utlede en formel for å øke antall anrop, for til slutt å utlede kompleksiteten ved å studere hva funksjonen gjør i tillegg til dens anrop rekursive. Jeg vil ikke snakke så mye om korreksjon lenger (bortsett fra helt til slutt), men ha tanken i bakhodet...

I det følgende vil C(n) angi kostnadene for funksjonen som er studert.

Enkle gjentakelser: C(n) = f(C(n-1))

Ordet "enkelt" her betyr ikke at kompleksi