Equazione "Divide et impera"
Salve a tutti. Voglio proporre il seguente esercizio:
Stabilire l'ordine di grandezza della seguente equazione:
$T(n)=5T(n/5)+n/(log_5n)$
Non so bene da dove iniziare dato che sono nuovo a questo tipo di esercizi. Nel testo che ho si parla di questo tipo di equazioni in maniera piuttosto particolare e solo in casi particolari. Potreste spiegarmi come procedere? Se avete da consigliarmi qualche testo dove affrontare bene queste cose, tanto meglio! Grazie
Stabilire l'ordine di grandezza della seguente equazione:
$T(n)=5T(n/5)+n/(log_5n)$
Non so bene da dove iniziare dato che sono nuovo a questo tipo di esercizi. Nel testo che ho si parla di questo tipo di equazioni in maniera piuttosto particolare e solo in casi particolari. Potreste spiegarmi come procedere? Se avete da consigliarmi qualche testo dove affrontare bene queste cose, tanto meglio! Grazie
Risposte
Potresti cominciare da wiki http://it.wikipedia.org/wiki/Teorema_principale_(informatica)
dopo di che il libro per eccellenza direi che è il Cormen (il libro è citato nella pagina wiki).
dopo di che il libro per eccellenza direi che è il Cormen (il libro è citato nella pagina wiki).
Ma siamo sicuri che quella particolare scelta di equazione di ricorrenza sia ben definita? Infatti $\lim_{n \to 1} \log_5 n = 0$.. Ma probabilmente mi sto perdendo in un bicchier d'acqua..
per materiale vedi anche qui.
Per la ricorrenza prova a cercare in questa sezione, ne son state risolte in mille modi diversi. Se avrai dubbi, dopo aver cercato, ne riparliamo.
In effetti hai ragione ma è subito risolto, il caso base lo ipotizziamo a costo costante e lo facciamo valere per $n<=1$ e via
Per la ricorrenza prova a cercare in questa sezione, ne son state risolte in mille modi diversi. Se avrai dubbi, dopo aver cercato, ne riparliamo.
"apatriarca":
:roll: Ma siamo sicuri che quella particolare scelta di equazione di ricorrenza sia ben definita? Infatti $\lim_{n \to 1} \log_5 n = 0$.. Ma probabilmente mi sto perdendo in un bicchier d'acqua..
In effetti hai ragione ma è subito risolto, il caso base lo ipotizziamo a costo costante e lo facciamo valere per $n<=1$ e via
Ho provato con i vostri link che sono senza dubbio utili ma non so se riesco a risolvere l'equazione. Ho che $a=5=b$ (nelle notazioni di wiki). Dunque $f(n)$ va più lentamente rispetto a $n^(log_ba)$. In qualche modo questo mi porterebbe a dire che $T(n)=\Theta(n)$ ma sono consideazioni qualitative, non sono affatto sicuro di quello che faccio.
Potreste aiutarmi? Grazie per la pazienza
Potreste aiutarmi? Grazie per la pazienza
"Albert Wesker 27":
Ho provato con i vostri link che sono senza dubbio utili ma non so se riesco a risolvere l'equazione. Ho che $a=5=b$ (nelle notazioni di wiki). Dunque $f(n)$ va più lentamente rispetto a $n^(log_ba)$.
In qualche modo questo mi porterebbe a dire che $T(n)=\Theta(n)$ ma sono consideazioni qualitative, non sono affatto sicuro di quello che faccio.
che caso hai preso in considerazione? se è il secondo direi che na va bene
$n/{log_5(n)} \in^{?} \Theta(n^{log_5(5)}*(log(n))^k)$
ma per esser vera $k=-1$ cosa non possibile perchè $k>=0$ (e per altri motivi simpatici...)
il caso da prendere in considerazione del master è il primo.
Sìsì ho preso in considerazione il primo caso =)
Per ora le equazioni del tipo sopra sembrano riuscire. Ho problemi invece in questa equazione divide et impera:
Stimare l'ordine di grandezza della seguente equazione:
$T(n)=2T(|sqrt(n)| ) + log(n)$
NB: $| |$ indicano la funzione parte intera inferiore che non sapevo inserire altrimenti.
Come posso apporcciare questo tipo di equazioni? Pensavo in qualche modo di ricondurmi al caso precedente tramite una sostituzione ma non so bene da che parte farmi. Grazie a tutti in anticipo.
Stimare l'ordine di grandezza della seguente equazione:
$T(n)=2T(|sqrt(n)| ) + log(n)$
NB: $| |$ indicano la funzione parte intera inferiore che non sapevo inserire altrimenti.
Come posso apporcciare questo tipo di equazioni? Pensavo in qualche modo di ricondurmi al caso precedente tramite una sostituzione ma non so bene da che parte farmi. Grazie a tutti in anticipo.
Ciao,
utilizzi una sostituzione di variabili tipo $log_2(n) = m$ con $n=2^m$.
attento da definire bene i casi base di validazione, la radice è un po' da formalizzare bene.
utilizzi una sostituzione di variabili tipo $log_2(n) = m$ con $n=2^m$.
attento da definire bene i casi base di validazione, la radice è un po' da formalizzare bene.
Come mai procedo con tale sostituzione? Qual è l'idea generale? Grazie mille ancora!
"Albert Wesker 27":
Come mai procedo con tale sostituzione? Qual è l'idea generale? Grazie mille ancora!
il perchè: ti semplifica i calcoli per ridursi a casi conosciuti e più malleabili come il Master.
Puoi benissimo calcolartela direttamente ma dovrai cimentarti con calcoli ben più complessi: post561116.html
Per questo quando si hanno come rami di ricorsione delle funzioni in $n$, si preferisce semplificare con la sostituzione di variabili. Per un'idea generale: post633316.html
Non dovrei procedere con la sostituzione $log(n)=m$? Non vedo perché utilizzare la base due per il logaritmo. Inoltre c'è la parte intera di mezzo. Non crea problemi?
"Albert Wesker 27":
Non dovrei procedere con la sostituzione $log(n)=m$? Non vedo perché utilizzare la base due per il logaritmo.
è una base come un'altra. Hai un logaritmo generico, è naturale in informatica caratterizzarlo con base $2$ quando si è in dubbio.
Infatti devi sostituire, è identico a questo: post633316.html
se linko qualcosa c'è un motivo!
se non comprendi dopo aver letto quel post, ne discutiamo.
Inoltre c'è la parte intera di mezzo. Non crea problemi?
nessun problema, nell'ipotesi di limitazione ce ne dimentichiamo.
Affrontiamo il caso della parte intera se applichiamo l'induzione.
Avevo aperto il link. Però lì c'era già nell'equazione di partenza un logaritmo in base due mentre qui no. per questo mi era venuto il dubbio che però è effettivamente superfluo.
Come avevo dimostrato nell'altra discussione postata da hamming_burst, il logaritmo in base due compare comunque già solo per via della presenza della radice quadrata. Avevo infatti dimostrato che il numero di iterazioni necessarie perché \( \lfloor \sqrt n \rfloor\) arrivi a \(1\) è proporzionale a \( \log_2 \log_2 n \) (è contenuto tra \(\log\log n\) e \(\log\log n + 1\) o qualcosa del genere se non ricordo male). Tecnicamente avrei potuto probabilmente usare una differente base per il logaritmo, ma avrebbe complicato calcoli e formula (la base viene naturale per via del \(2\) nell'esponente della radice quadrata*).
* Fosse ad esempio stata la radice cubica sarebbe probabilmente stato più comodo usare la base \(3\) per il logaritmo.
* Fosse ad esempio stata la radice cubica sarebbe probabilmente stato più comodo usare la base \(3\) per il logaritmo.
Forse c'è stato un equivoco.
Io mi riferivo al metodo della sostituzione di variabili: post633316.html
Quello che ho linkato con post561116.html era solo un'esempo di calcolo diretto con il metodo dell'albero. Era solo per far vedere la differenza/difficoltà e del perchè si introduce il metodo della sostituizione di variabili, che con due passaggi risolve tutto.
Si può far tutto, ma se non ci si vuol far del male e non si è perversi, non si utilizzano metodi come l'albero o iterazione (come abbiam fatto io ed apatriarca ) quando c'è di mezzo la radice.
Io mi riferivo al metodo della sostituzione di variabili: post633316.html
Quello che ho linkato con post561116.html era solo un'esempo di calcolo diretto con il metodo dell'albero. Era solo per far vedere la differenza/difficoltà e del perchè si introduce il metodo della sostituizione di variabili, che con due passaggi risolve tutto.
Si può far tutto, ma se non ci si vuol far del male e non si è perversi, non si utilizzano metodi come l'albero o iterazione (come abbiam fatto io ed apatriarca
) quando c'è di mezzo la radice.
A meno di dare per scontato che la profondità dell'albero o dell'iterazione sia \(\log\log n\)...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo