Metodo di sostituzione per la risoluzione di una ricorrenza

[dlbp]

Salve a tutti...ho ripreso a studiare dopo l'estate e mi sono imbattuto in un piccolo problema. Devo dimostrare che la ricorrenza è un . Riguarda il calcolo del tempo di esecuzione di un algoritmo.

Ho tentato di procedere secondo il metodo di sostituzione. Ottengo:


Però non riesco a capire come procedere ora a dimostrare che il tempo di esecuzione è un .

Mi servirebbe una mano. Grazie mille

[fairyvilje]

Il metodo più veloce è applicare lui
http://it.wikipedia.org/wiki/Teorema_principale_%28informatica%29

Provaci e dicci se ti riesce.

[dlbp]

fairyvilje purtroppo ho provato ad applicare anche questo metodo ma invano dato che non l'ho mai usato. Potresti farmi vedere a quella ricorrenza come si applicano sia il metodo di sostituzione sia quello del teorema dell'esperto?

Grazie mille. Non riesco proprio a capire come venirne fuori. Ci sto provando da stamane

[fairyvilje]

Non ho molto tempo in questi giorni sto preparando esami. Mi dispiace, ma ti lascio un pdf
http://www.dmi.unict.it/~cutello/ricorrenza.pdf
Presenta i tre metodi principali spiegati in modo molto veloce e con delle applicazioni negli esempi.
Prova a seguirli sulla falsariga, posta i conti e poi li vediamo insieme.
Non so che corso di laurea frequenti ma il teorema che ti ho linkato se fai queste cose sarà tuo amico. Ti consiglio di perderci un po' di tempo a studiarlo e capirlo bene, risolve la maggior parte dei problemi che ti possono essere posti in modo immediato.

[dlbp]

fairyvilje buongiorno. poiché la ricorrenza che ho postato ieri è uguale ad una presente sul pdf, ho seguito il suo principio di risoluzione. Mi trovo con i calcoli. Sul pdf dice che è un e mi trovo con i calcoli. Quindi è sbagliato dire che è un .

Grazie mille.

P.s. Il pdf è molto utile. L'ho anche appena stampato!

[fairyvilje]

Al contrario la classe degli include quelle quindi è perfettamente giusto!
Ricordati il significato di ovvero cresce meno rispetto ad una qualche . Se applichi la definizione alle due notazioni precedenti vedrai che entrambe sono valide, anche se una migliora il risultato trovato rispetto all'altra :)

[dlbp]

Riesumo questo post per un piccolo dubbio.
Se ho la seguente somma: , il risultato (sempre in notazione asintotica) quant'è?
Suppongo che sia uguale per entrambi i termini :)

[fairyvilje]

Il valore di n è irrilevante proprio perché si guarda il comporamento asintotitco. Ti invito a riflettere sulle definizioni perché la risposta è davvero immediata.

[dlbp]

Io sono convinto che sia . Poi magari mi sbaglio...e se mi sbaglio sarei curioso di sapere il perché

[fairyvilje]

Certo che si. Magari argomenta la risposta :)