Complexiteit en recursieve functies

> LeekScript-zelfstudie

Waarschuwing: Dit artikel is wiskundig intensief (althans voor deze wiki). Niet gebruiken zonder medisch advies.

Serieuzer: hier ga ik proberen te praten over de Optimalisatie van recursieve functies (The_Recursion). Dit artikel is meer voor mensen die geïnteresseerd zijn in functioneel programmeren en programmeertheorie.

Het is niet altijd gemakkelijk om bij het schrijven van een recursieve functie te weten hoeveel aanroepen we zullen doen voordat we tot het resultaat komen. Of zelfs als we soms tot het resultaat komen. De tutorial over La_Récursivité geeft manieren om recursieve functies te optimaliseren, maar bestudeert geen complexiteit of correctie; Ik zal daarom hier met voorbeelden enkele methodes illustreren om je weg te vinden.

Deze lijst met voorbeelden is niet bedoeld om uitputtend te zijn, het zal voor elk van uw algoritmen nodig zijn om de uitgevoerde bewerkingen nauwkeurig te onderzoeken.

Vervolgens is het aan jou om deze ideeën te kopiëren voor je persoonlijke algoritmen, en als je andere voorbeelden vindt die het vermelden waard zijn, leg ze dan hier uit!

Eerste voorbeelden

Sommige eenvoudige recursieve functies hebben een gemakkelijk te bestuderen complexiteit. Dit is het geval bij het eerste voorbeeld van de tutorial over recursie:

functie somN(n) { als (n === 0) { geef 0 terug; } anders { geef n + somN(n - 1); } }

Ici, c'est assez simple : on voit facilement que si on donne un entier n (positif !) à cette fonction, elle va ajouter n à la somme de 0 à n-1, qu'elle calcule en s'appelant elle- zelfde. We gaan dus n + (n-1 + ... + (0)...) doen, wat n optellingen en n functieaanroepen maakt, d.w.z. een complexiteit van O( n).

Als we echter een negatief geheel getal als invoer geven, zal deze functie een stapeloverloop veroorzaken: het zal negatieve getallen optellen zonder ooit 0 te bereiken. Evenzo, als we een niet-geheel getal geven, zullen we nooit 0 bereiken door meerdere keren 1 af te trekken . Let dus op de '''correctie''' van je recursieve functies: als je niet alle gevallen hebt voorzien of als je ze gebruikt met een invoer die niet overeenkomt met wat je in gedachten had bij het coderen, had je onaangename verrassingen.

De optimalisatiehandleiding geeft een voorbeeld van een O(2^n) complexiteitsfunctie:

functie getAllCombos(lijst_items){ var nb_items = aantal(lijst_items);

als(nb_items == 1) { return [[], lijst_items]; }

var sub_lijst = subArray(lijst_items, 1, nb_items - 1); var partiële_combos_list = getAllCombos(sub_list); // Recursieve aanroep var m = count(list_combos_partial);

// Vervolgens dupliceren we de lijst met combo's: we behouden degene die we hadden en we voegen dezelfde toe met het eerste element van liste_items voor(var i=0; i P(n) = 2*P(n-1). Omdat we ook P(1) = 2 hebben, krijgen we de formule P(n) = 2 * ... * 2 = 2^n, vandaar de (bij minste) exponentiële complexiteit. We kunnen dan aantonen dat deze functie een exponentiële complexiteit heeft (en niet groter): elke aanroep van de functie creëert een array van grootte n-1 met subArray (kosten: O(n )), duwt m dan met m de grootte van de gedeeltelijke combo-array, d.w.z. 2^(n-1) (kosten: K * 2^(n-1) met K de push kosten), wat de kosten van de subArray verplettert, en dus leidt tot een complexiteit die wordt bepaald door het aantal P(n) uitgevoerde pushes.

Het is dit idee dat ik hier zal ontwikkelen: verkrijg een herhalingsformule en probeer een formule af te leiden om het aantal aanroepen te verhogen, om uiteindelijk de complexiteit af te leiden door te bestuderen wat de functie doet naast zijn recursieve aanroepen. Ik zal het niet meer zo vaak over correctie hebben (behalve aan het einde), maar houd het idee in gedachten...

Hierna geeft C(n) de kosten van de bestudeerde functie aan.

Eenvoudige recidieven: C(n) = f(C(n-1))

Het woord "simpel" betekent hier niet dat de complexi