Monimutkaisuus ja rekursiiviset funktiot

> LeekScript-opetusohjelma

Varoitus: Tämä artikkeli on matemaattisesti intensiivinen (ainakin tälle wikille). Älä käytä ilman lääkärin neuvoja.

Vakavammin: tässä yritän puhua rekursiivisten funktioiden Optimoinnista (The_Recursion). Tämä artikkeli on enemmän ihmisille, jotka ovat kiinnostuneita toiminnallisesta ohjelmoinnista ja ohjelmointiteoriasta.

Rekursiivista funktiota kirjoitettaessa ei ole aina helppoa tietää, kuinka monta puhelua teemme ennen kuin pääsemme tulokseen. Tai vaikka joskus päästäänkin tulokseen. La_Récursivité:n opetusohjelma tarjoaa tapoja optimoida rekursiivisia funktioita, mutta se ei tutki monimutkaisuutta tai korjauksia; Siksi havainnollistan tässä esimerkeillä joitain menetelmiä löytääksesi paikan.

Tätä esimerkkiluetteloa ei ole tarkoitettu tyhjentäväksi, vaan jokaisen algoritmin on tutkittava tarkasti suoritetut toiminnot.

Sitten sinun on kopioitava nämä ideat henkilökohtaisiin algoritmeihisi, ja jos löydät muita mainitsemisen arvoisia esimerkkejä, selitä ne täällä!

Ensimmäiset esimerkit

Jotkin yksinkertaiset rekursiiviset funktiot ovat helposti tutkittavia monimutkaisia. Tämä on esimerkki rekursio-opetusohjelman ensimmäisestä esimerkistä:

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

Tässä asia on melko yksinkertainen: voimme helposti nähdä, että jos annamme tälle funktiolle kokonaisluvun n (positiivinen!), se lisää n:n summaan 0 arvoon n-1, jonka se laskee kutsumalla itseään parilliseksi. Joten aiomme tehdä n + (n-1 + ... + (0)...), joka tekee n lisäystä ja n funktiokutsua, eli O( n).

Jos kuitenkin annamme syötteeksi negatiivisen kokonaisluvun, tämä funktio aiheuttaa pinon ylivuodon: se lisää negatiivisia lukuja saavuttamatta koskaan nollaa. Vastaavasti, jos annamme ei-kokonaisluvun, emme koskaan saavuta 0:ta vähentämällä 1 useita kertoja . Kiinnitä siis huomiota rekursiivisten funktioidesi ''''korjaukseen'': jos et ole ennakoinut kaikkia tapauksia tai jos käytät niitä syötteellä, joka ei vastaa sitä, mitä ajattelit koodattaessasi, olisit voinut epämiellyttäviä yllätyksiä.

Optimoinnin opetusohjelmassa on esimerkki O(2^n)-monimutkaisuusfunktiosta:

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

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

var aliluettelo = alitaulukko(luettelo_kohteet, 1, nb_kohteet - 1); var partial_combos_list = getAllCombos(alilista); // Rekursiivinen puhelu var m = count(list_combos_partial);

//Tämän jälkeen kopioimme yhdistelmäluettelon: säilytämme ne, jotka meillä oli, ja lisäämme samat listan_items ensimmäisen elementin kanssa for(var i=0; i P(n) = 2*P(n-1). Koska meillä on myös P(1) = 2, saamme kaavan P(n) = 2 * ... * 2 = 2^n, joten (at vähintään) eksponentiaalinen monimutkaisuus. Voimme sitten osoittaa, että tällä funktiolla on eksponentiaalinen monimutkaisuus (eikä suurempi): jokainen funktion kutsu luo taulukon, jonka koko on n-1 subArray:lla (hinta: O(n )), painaako m m:llä osittaisen yhdistelmätaulukon kokoa, eli 2^(n-1) (hinta: K * 2^(n-1), kun K paina kustannus), mikä murskaa alitaulukon kustannukset ja johtaa siten monimutkaisuuteen, jonka määrittää suoritettujen työntöjen lukumäärä P(n).

Juuri tätä ajatusta kehitän tässä: hanki toistuvuuskaava ja yritä päätellä kaava kutsujen määrän lisäämiseksi, lopuksi päätellä monimutkaisuus tutkimalla mitä funktio tekee rekursiivisten kutsujensa lisäksi. En puhu enää niin paljon korjauksesta (paitsi aivan lopussa), mutta pidä ajatus mielessä...

Seuraavassa C(n) merkitsee tutkitun funktion kustannuksia.

Yksinkertaiset toistuvat: C(n) = f(C(n-1))

Sana "yksinkertainen" ei tarkoita, että kompleksi