ElectroYou

Salve a tutti...ho ripreso a studiare dopo l'estate e mi sono imbattuto in un piccolo problema. Devo dimostrare che la ricorrenza $T(n)=3 T(\frac{n}{2})+n$ è un O(n^2)

. Riguarda il calcolo del tempo di esecuzione di un algoritmo.

Ho tentato di procedere secondo il metodo di sostituzione. Ottengo:
$T(n) <= \frac{3}{4} c n^2 + n$

Però non riesco a capire come procedere ora a dimostrare che il tempo di esecuzione T(n)

è un

.

Mi servirebbe una mano. Grazie mille

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

Provaci e dicci se ti riesce.

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

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.

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 $O(n^{log_2 3})$ e mi trovo con i calcoli. Quindi è sbagliato dire che è un O(n^2)

.

Grazie mille.

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

Al contrario la classe degli O(n^2)

include quelle $O(n^{log3})$ quindi è perfettamente giusto!
Ricordati il significato di O(n^k)

ovvero cresce meno rispetto ad una qualche a_1n^k

. Se applichi la definizione alle due notazioni precedenti vedrai che entrambe sono valide, anche se una migliora il risultato trovato rispetto all'altra :)

Riesumo questo post per un piccolo dubbio.
Se ho la seguente somma: $O(n)+\Theta(n)$ , il risultato (sempre in notazione asintotica) quant'è?
Suppongo che

sia uguale per entrambi i termini :)

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

Io sono convinto che sia $\Theta(n)$ . Poi magari mi sbaglio...e se mi sbaglio sarei curioso di sapere il perché

Certo che si. Magari argomenta la risposta :)

ElectroYou

Metodo di sostituzione per la risoluzione di una ricorrenza

Metodo di sostituzione per la risoluzione di una ricorrenza

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre

Re: Metodo di sostituzione per la risoluzione di una ricorre