Relazione di ricorrenza, definizione

La misurazione del tempo (complessita' di un algoritmo) avviene tramite il conteggio delle istruzioni macchina eseguite, nelle funzioni ricorsive si contano anche le linee di codice (istruzioni) mandate in esecuzione dalle chiamate ricorsive della stessa funzione.
La relazione di ricorrenza esprime questo calcolo in formula.

Es, la relazione di ricorrenza di Fibonacci: T(n) = 2 + T(n-1) + T(n-2)

E' possibile risolvere le relazioni di ricorrenza attraverso 3 metodi: Il metodo iterativo, della sostituzione, e tramite il teorema fondamentale delle ricorrenze.
Il metodo iterativo consite nello srotolare la relazione di ricorrenza considerando la variabile c menzionata nelle definizioni delle limitazioni superiori e inferiori (O grande e Omega grande) in modo tale da contare quante volte si svolge il procedimento, quindi nel caso della relazione di ricorrenza della ricerca binaria, che e' T(n)=c+T(n/2) per n>1 e T(n)=1 per n=1 si considera c multiplo di due e si srotola la ricorsione cosi':

T(n)=c+T(n/2)=2c+T(n/4)=...=ic+T(n/2^i)

per essere n/2^i bisogna svolgere il procedimento i=logn volte, quindi T(n)=O(logn)


Il metodo della sostituzione tratta di indovinare la soluzione e dimostrarla tramite induzione, quindi dopo aver determinato i caso base bisogna applicare il passo induttivo per calcolare i valori della variabile c per i quali e' valida la ricorrenza, per determinare le limitazioni inferiori o superiori.

Il teorema fondamentale delle ricorrenze si applica agli algoritmi che seguono la tecnica "divide et impera", con relazioni di ricorrenza del tipo T(n)=aT(n/b) + f(n), a seconda della forma di f(n) presenta tre soluzioni diverse. (vedi definizione teorema master).