Complessità e funzioni ricorsive

> Esercitazione LeekScript

Attenzione: Questo articolo è matematicamente intensivo (almeno per questo wiki). Non utilizzare senza consiglio medico.

Più seriamente: qui cercherò di parlare dell'Ottimizzazione delle funzioni ricorsive (The_Recursion). Questo articolo è più per le persone interessate alla programmazione funzionale e alla teoria della programmazione.

Non è sempre facile, quando si scrive una funzione ricorsiva, sapere quante chiamate faremo prima di arrivare al risultato. O anche se arriveremo al risultato, a volte. Il tutorial su La_Récursivité fornisce modi per ottimizzare le funzioni ricorsive, ma non studia la complessità o la correzione; Illustrerò quindi qui con esempi alcuni metodi per orientarsi.

Questo elenco di esempi non vuole essere esaustivo, sarà necessario che ogni vostro algoritmo esamini con precisione le operazioni effettuate.

Poi sta a te copiare queste idee per i tuoi algoritmi personali, e se trovi altri esempi degni di nota, spiegali qui!

Primi esempi

Alcune semplici funzioni ricorsive hanno una complessità facile da studiare. Questo è il caso del primo esempio del tutorial sulla ricorsione:

function sommaN(n) { if (n === 0) { return 0; } else { return n + sommaN(n - 1); } }

Qui è abbastanza semplice: possiamo vedere facilmente che se diamo un numero intero n (positivo!) a questa funzione, essa aggiungerà n alla somma da 0 a n-1, che calcola chiamandosi pari. Quindi faremo n + (n-1 + ... + (0)...), che fa n addizioni e n chiamate di funzione, cioè una complessità di O( n).

Tuttavia, se diamo un numero intero negativo come input, questa funzione causerà un overflow dello stack: aggiungerà numeri negativi senza mai arrivare a 0. Allo stesso modo, se diamo un numero non intero, non raggiungeremo mai 0 sottraendo 1 più volte . Quindi fai attenzione alla '''correzione''' delle tue funzioni ricorsive: se non hai previsto tutti i casi o se le utilizzi con un input che non corrisponde a quello che avevi in mente codificandolo, potresti avere spiacevoli sorprese.

Il tutorial sull'ottimizzazione fornisce un esempio di una funzione di complessità O(2^n):

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

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

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

//Dopodiché duplichiamo la lista delle combo: manteniamo quelle che avevamo, e aggiungiamo le stesse con il primo elemento di liste_items for(var i=0; i P(n) = 2*P(n-1). Poiché abbiamo anche P(1) = 2, otteniamo la formula P(n) = 2 * ... * 2 = 2^n, quindi la (a minima) complessità esponenziale. Possiamo quindi dimostrare che questa funzione ha una complessità esponenziale (e non maggiore): ogni chiamata alla funzione crea un array di dimensione n-1 con subArray (costo: O(n )), quindi m spinge con m la dimensione dell'array combo parziale, cioè 2^(n-1) (costo: K * 2^(n-1) con K la spinta cost), che abbatte il costo del subArray, e quindi porta a una complessità determinata dal numero P(n) di push eseguiti.

È questa idea che svilupperò qui: ottenere una formula di ricorrenza e provare a dedurre una formula per aumentare il numero di chiamate, per dedurre infine la complessità studiando cosa fa la funzione oltre alle sue chiamate ricorsive. Non parlerò più tanto della correzione (tranne che alla fine), ma tenete a mente il concetto...

Nel seguito, C(n) indicherà il costo della funzione studiata.

Ricorrenze semplici: C(n) = f(C(n-1))

La parola "semplice" qui non significa che i complessi