Albero di ricorsione, risoluzione di equazioni di ricorrenza

Question

Per quanto ne so ci sono 4 modi per risolvere le equazioni di ricorrenza:1- Alberi di ricorsione 2- Sostituzione 3 - Iterazione 4 - Derivato

Ci viene chiesto di utilizzare la sostituzione, di cui avremo bisogno per indovinare una formula per l'output.Ho letto dal libro CLRS che non esiste alcuna magia per farlo, ero curioso di sapere se ci sono delle euristiche per farlo?

Posso certamente avere un'idea disegnando un albero delle ricorrenze o utilizzando l'iterazione ma, poiché l'output sarà in formato Big-OH ​​o Theta, le formule non corrispondono necessariamente.

Qualcuno ha qualche consiglio per risolvere le equazioni di ricorrenza utilizzando la sostituzione?

Answer 1

Per quelli semplici, basta fare un'ipotesi "ragionevole".

Per quelli più complicati, andrei avanti e utilizzerei un albero delle ricorrenze: mi sembra l'algoritmo più semplice per generare un'ipotesi.Tieni presente che può essere difficile utilizzare un albero delle ricorrenze per dimostrare un limite (i dettagli sono difficili da ottenere correttamente).Gli alberi delle ricorrenze sono molto utili per formulare ipotesi che vengono poi dimostrate mediante sostituzione.

Non sono sicuro del motivo per cui stai dicendo che le formule non corrisponderanno all'output in Big-O o Theta.Solitamente non corrispondono esattamente, ma questo è parte dello scopo di Big-O.Parte del trucco per tornare alla sostituzione è sapere come inserire la soluzione Big-O per far funzionare l'algebra di sostituzione.IIRC, CLRS risolve uno o due esempi di questo.

Answer 2

Tieni presente che l'elenco dei possibili modi per risolvere le equazioni di ricorrenza non è sicuramente completo, è semplicemente un insieme di strumenti che insegnano agli informatici, perché molto probabilmente risolveranno la maggior parte dei tuoi problemi.

Per soluzioni esatte di equazioni ricorrenti i matematici utilizzano uno strumento chiamato funzioni generatrici.Le funzioni generatrici forniscono soluzioni esatte e in generale sono più potenti del teorema principale.

C'è una grande risorsa online per saperne di più qui. http://www.math.upenn.edu/~wilf/DownldGF.html

Se segui i primi due esempi dovresti capirlo in pochissimo tempo.

Hai bisogno di conoscenze di matematica e di comprendere le serie rudimentali di Taylor. http://en.wikipedia.org/wiki/Taylor_series

Le funzioni generatrici sono anche estremamente utili in probabilità.