[Algoritmi] Come si risolvono le equazioni di ricorrenza?

[Feibio93]

Ciao a tutti! A breve ho un esame di algoritmi e non ho capito quasi nulla riguardo le equazioni di ricorrenza... So che sono funzioni di costo per trovare il costo di un algoritmo ricorsivo, ma come si risolvono? Ci sono i 3 modi possibili della sostituzione, o l'albero di ricorrenza o il master theorem, ma come si fa a capire qual è quello da applicare? Qual è il ragionamento da fare all'inizio?
Grazie mille per il tempo che dedicate!

[apatriarca]

Anche se le equazioni di ricorrenza compaiono spesso nel calcolo del costo degli algoritmi, non sono limitate a questo ambito. Possono infatti comparire anche in altre situazioni. Si tratta principalmente di funzioni che sono definite in funzione di se stesse e che compaiono quindi sia a destra che a sinistra dell'uguale. Per quanto riguarda i metodi di risoluzione, il master theorem è in generale il più potente e se è possibile applicarlo vale certamente la pena di farlo. Ti fornisce infatti una risposta immediata, senza la necessità di fare ulteriori calcoli. La sostituzione è principalmente comoda quando ci sono funzioni esponenziali/logaritmi nelle chiamate ricorsive. L'albero di ricorrenza quando si hanno divisioni/prodotti. Il telescoping quando hai somme/sottrazioni. Ma alla fine si tratta più che altro di fare un po' di esercizi e prendere dimestichezza con i vari metodi e con l'esperienza arriverai a capire quale usare nelle varie circostanze. Nota comunque che è spesso possibile usare tanti metodi per arrivare alla soluzione. La differenza sta principalmente nella semplicità dei calcoli. Ci sono delle ricorrenze in cui hai dubbi?

[Feibio93]

Ok, grazie mille! Comunque sono dubbi in generale più che nello specifico... Per esempio, ho:

T(n)= T(n/2)+2^n n>1
1 n<=1

L'esercizio chiede di usare il metodo di sostituzione. C'è la soluzione, che dice "E' facile osservare che il limite inferiore è \Theta(2^n), poi c'è la risoluzione per trovare il limite superiore, che è anch'esso O(2^n). Ma in base a cosa si decide che è 2^n? Per esempio, se avessi provato per n, come faccio a sapere se è sbagliato? Qual'è un modo per verificare che la soluzione sia corretta? Grazie mille

P.S. Non ho idea di come inserire il linguaggio matematico giusto, mi sono iscritto ieri Ho provato "Simboli LaTeX" m a quanto pare non ha funzionato