Master Theorem Ricorsione - Esercizio
Ciao, sono nuovo di questo forum, vi chiedo se qualcuno mi sa dare alcune dritte si come risolvere alcuni esercizi sulla ricorsione.
Vi posto un'immagine con il testo dell'esercizio.
In particolare se qualcuno mi riuscisse a spiegare un po' meglio anche come risolvere questo tipo di esercizi in modo generale.
Vi ringrazio anticipatamente!!
Vi posto un'immagine con il testo dell'esercizio.
In particolare se qualcuno mi riuscisse a spiegare un po' meglio anche come risolvere questo tipo di esercizi in modo generale.
Vi ringrazio anticipatamente!!
Risposte
Ciao,
ma devi per forza usa il Master?
Se hai già le soluzioni, li puoi usare con il Metodo della sostituzione (metodo per tentavi), cioè provi per induzione quale sia quella corretta.
E' una strada lunga, ma è un'idea.
Ma anche essendo che sei nel mondo asintotico, puoi provare prima a fare qualche maggiorazione o minorazione, per vedere qualche complessità più si avvicina, e qua puoi usare il Master.
Quelle variabili f(n) + g(n) devi cercarle di metterle insieme o toglierle, con l'idea sopra puoi provare.
Se hai dubbi, basta chiedere
PS: se hai dubbi su queste tecniche prova a cercare in questa sezione, ho già risolto in passato e fatto vedere tutti i passaggi di varie equazioni.
ma devi per forza usa il Master?
Se hai già le soluzioni, li puoi usare con il Metodo della sostituzione (metodo per tentavi), cioè provi per induzione quale sia quella corretta.
E' una strada lunga, ma è un'idea.
Ma anche essendo che sei nel mondo asintotico, puoi provare prima a fare qualche maggiorazione o minorazione, per vedere qualche complessità più si avvicina, e qua puoi usare il Master.
Quelle variabili f(n) + g(n) devi cercarle di metterle insieme o toglierle, con l'idea sopra puoi provare.
Se hai dubbi, basta chiedere
PS: se hai dubbi su queste tecniche prova a cercare in questa sezione, ho già risolto in passato e fatto vedere tutti i passaggi di varie equazioni.
Ti ringrazio della risposta, domani andrò sicuramente a spulciare questa sezione.
Ma ora vorrei capire un'attimo una cosa, almeno se ragiono nel modo corretto.
Io so che il $ b*T(n/3) $ mi diventa $ n^log b $ con base 3 (non so scriverlo) e quindi devo fissando un b trovare l'esponente di n per poterlo confrontare con il resto dell'espressione, cioè f(n).
Ora so che asintoticamente $ 2*n^2 $ è più debole del resto della formula, quindi potrei escluderlo e concentrarmi solo sul $ 100*n*root()(n)*log^2 n $ ???
Se così fosse non mi spiego perchè il risultato numero 2 sia $ n*root()(n) log^3 n $ non dovrebbe essere solo $ n*root()(n) log^2 n $ ??
Grazie!!!
Ma ora vorrei capire un'attimo una cosa, almeno se ragiono nel modo corretto.
Io so che il $ b*T(n/3) $ mi diventa $ n^log b $ con base 3 (non so scriverlo) e quindi devo fissando un b trovare l'esponente di n per poterlo confrontare con il resto dell'espressione, cioè f(n).
Ora so che asintoticamente $ 2*n^2 $ è più debole del resto della formula, quindi potrei escluderlo e concentrarmi solo sul $ 100*n*root()(n)*log^2 n $ ???
Se così fosse non mi spiego perchè il risultato numero 2 sia $ n*root()(n) log^3 n $ non dovrebbe essere solo $ n*root()(n) log^2 n $ ??
Grazie!!!
per poter usare il Master devi avere questo tipo di equazioni: $aT(n/b) + f(n)$ con f(n) asintoticamente simile a $n^(log_b(a))$
se devi usarlo puoi cercare di trasformare l'equazione: $f(n) = 2n^2 + 100nsqrt(n)log^2 in O(nsqrt(n)log^2(n))$
o sincaso fai quello che ti ho suggerito sopra, maggiori e minori per avvicinarti asintoticamente alla soluzione:
esempio:
$T(n) = bT(n/3) + 2n^2 + 100nsqrt(n)log^2(n) <= bT(n/3) + 100nsqrt(n)log^3(n)$ (da dimostrare)
quello che hai fatto te è sbagliato se "togli" cerchi una limitazione inferiore:
$bT(n/3) + 2n^2 + 100nsqrt(n)log^2(n) >= bT(n/3) + 100nsqrt(n)log^2(n)$
domanda: conosci le limitazioni $O(),\ Omega(),\ Theta()$ e le loro proprietà?
vado a naso, non ho fatto conti, prova. (una strada che seguo molte volte io è usare l'induzione, li stai sicuro che trovi la complessità).
se devi usarlo puoi cercare di trasformare l'equazione: $f(n) = 2n^2 + 100nsqrt(n)log^2 in O(nsqrt(n)log^2(n))$
o sincaso fai quello che ti ho suggerito sopra, maggiori e minori per avvicinarti asintoticamente alla soluzione:
esempio:
$T(n) = bT(n/3) + 2n^2 + 100nsqrt(n)log^2(n) <= bT(n/3) + 100nsqrt(n)log^3(n)$ (da dimostrare)
quello che hai fatto te è sbagliato se "togli" cerchi una limitazione inferiore:
$bT(n/3) + 2n^2 + 100nsqrt(n)log^2(n) >= bT(n/3) + 100nsqrt(n)log^2(n)$
domanda: conosci le limitazioni $O(),\ Omega(),\ Theta()$ e le loro proprietà?
vado a naso, non ho fatto conti, prova. (una strada che seguo molte volte io è usare l'induzione, li stai sicuro che trovi la complessità).
mmmm purtroppo ho poco materiale su queste cose, riesci a darmi qualche dritta sulle proprietà e come maggiorare e minorare?
Grazie 1000
Grazie 1000
Bhe non posso spiegarti cosa siano, c'è molto materiale che spiega la definizione:
es:
http://en.wikipedia.org/wiki/Big_O_notation
https://www.matematicamente.it/forum/i-s ... 66257.html (fatto da gugo82)
per i metodi: https://www.matematicamente.it/forum/pos ... tml#479901 guarda "Equazioni di ricorrenza"
Se hai domande chiedi pure
PS: ma l'esercizio del post viene da qualche corso, o da un libro?
es:
http://en.wikipedia.org/wiki/Big_O_notation
https://www.matematicamente.it/forum/i-s ... 66257.html (fatto da gugo82)
per i metodi: https://www.matematicamente.it/forum/pos ... tml#479901 guarda "Equazioni di ricorrenza"
Se hai domande chiedi pure
PS: ma l'esercizio del post viene da qualche corso, o da un libro?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo