Le equazioni di ricorrenza vengono utilizzate per stabilire il costo computazionale di un frammento di codice in cui vi sia la ricorsione.
Nel primo esempio che hai fatto, non c'è bisogno di utilizzare una formula di ricorrenza. come puoi verificare su un qualsiasi testo di algoritmi, il costo di un algoritmo può essere calcolato come costo di ogni singola istruzione; se ci sono cicli for basta calcolare il costo del corpo del ciclo e moltiplicarlo per il numero di volte in cui il ciclo viene ripetuto.
Prima di parlare di complessità bisogna valutare cosa si intende per complessità. Nel caso dei tuoi esempi, sono algoritmi basati sui confronti, quindi per complessità intenderemo il numero di confronti effettuati dall'algoritmo.
Bisognerebbe anche fare delle valutazioni sul comportamento dell'algoritmo sui dati e valutare se calcolare il comportamento dell'algoritmo nel caso peggiore, nel caso migliore o nel caso medio.
Alcuni algoritmi, ad esempio proprio il quicksort, hanno un comportamento particolare.
L'analisi del caso peggiore del quicksort porta ad una valutazione di una complessità dell'ordine O(n^2).
Ma analizzando i tempi medi di esecuzione, ci si accorge che l'algoritmo ha una complessità O(n log n) decisamente più favorevole.
Per questo tralascerò l'esempio del quicksort (sarebbe stato meglio un esempio basato sull'algoritmo di mergesort, più semplice da esaminare) e analizzerò i primi due algoritmi nel caso peggiore: l'array contiene n elementi e non ci sono elementi consecutivi la cui somma è 1. in questo caso l'algoritmo restituisce false solo dopo aver esaminato l'intero array.
Partiamo dalla versione non ricorsiva. In questo caso, come ho già detto, non è necessaria la formula di ricorrenza. Basta calcolare il costo, riga per riga della funzione.
Consideriamo costante il costo della chiamata a funzione che viene effettuato una volta sola
nella riga seguente abbiamo 2 confronti, che vengono eseguiti solo una volta all'inizio, quando la funzione viene chiamata
Codice:
if(a.length == 1 || a.length == 0) return false;
qui abbiamo un ciclo for, e in ogni passo del ciclo confrontiamo se i è < del numero di elementi quindi: 1 confronto ripetuto n volte
Codice:
for(int i = 0; i<a.length; i++){
nella riga successiva abbiamo di nuovo un confronto. anche in questo caso, il confronto è ripetuto n volte
Codice:
if(i != a.length -1){
ancora un altro confronto, e ancora una volta questo confronto è ripetuto n volte (in effetti potremmo valutare soltanto questa operazione come obiettivo del calcolo della complessità... ma non cambieremmo l'ordine di grandezza della complessità della funzione)
Codice:
if(a[i] + a[i + 1] == 1)return true;
il costo totale è quindi
dove c è il costo della chiamata a funzione e del return finale.
in definitiva il comportamento della funzione è lineare rispetto alla grandezza del vettore in ingresso è dunque O(n)
ripetiamo lo stesso procedimento per la funzione ricorsiva
abbiamo il costo della chiamata a funzione, che consideriamo costante [EDIT]: qui per chiamata a funzione non intendo il costo della chiamata ricorsiva ma l'insieme delle operazioni che vengono effettuate sullo stack quando c'è una chiamata a funzione!!!!
Anche in questo caso, abbiamo un confronto all'inizio della funzione
Codice:
if(i == a.length - 1)return false;
poi abbiamo un nuovo confronto
Codice:
if(a[i] + a[i + 1] == 1)return true;
e qui sorge il problema
Codice:
return prova2(a, i + 1);
non possiamo dire quanto costa questa chiamata, perchè il costo della funzione ricorsiva è proprio l'incognita che stiamo cercando.
Per questo, ci facciamo aiutare dalle formule di ricorrenza: definisco t[j] il costo della chiamata della funzione su j elementi.
In assoluto non so quanto valga t[j] ma posso fare delle valutazioni.
Per prima cosa osservo il costo della base della ricorsione: si ha banalmente la chiamata su un array di un solo elemento e la funzione restituisce false alla prima riga, quindi dopo il primo confronto
T[1]=O(1);
nel passo ricorsivo, su un array di n elementi posso osservare che effettuo 2 confronti e poi faccio una chiamata riducendo di 1 elemento la dimensione dell'array quindi posso sicuramente scrivere che
t[n]=2+t[n-1]
in definitiva il mio costo è definito dalla seguente equazione di ricorrenza
Codice:
t[n] =O(1) per n=1;
=2+t[n-1] per n>1;
A questo punto, usando il metodo iterativo possiamo risolvere l'equazione di ricorrenza:
t[n]=2+t[n-1]
ma, applicando l'equazione di ricorrenza a t[n-1] possiamo scrivere
t[n-1]=2+t[n-2]
sostituendo
si ha
t[n]=2+t[n-1]=2+2+t[n-2]
iterando ancora
t[n]=2+t[n-1]=2+2+t[n-2]=2+2+2+t[n-3]
Osserva che il numero di volte in cui compare il valore 2 corrisponde al valore che sottraggo ad n in ogni iterazione.
quindi in generale si avrà
t[n]=i*2+t[n-i]
Ti ricordo che stiamo esaminando il caso peggiore, quindi la chiamata ricorsiva terminerà quando avremo completato l'array ovvero quando i=n-1 e in quel caso il costo della chiamata sarà quello della base della ricorsione, ovvero t[1]=O(1);
quindi sostituendo avremo
t[n]=(n-1)*2+t[n-(n-1)]=(n-1)*2+t[1]=O(n)
anche in questo caso la complessità è lineare.
spero di essere stato sufficientemente chiaro...