[Algoritmi]Ricorrenza Metodo Di Sostituzione
ciao a tutti
mi sto preparando per l'esame di algoritmi e
non riesco a capire come risolvere le ricorrenze con il metodo di sostituzione..
per esempio mi potete spiegare senza saltare i passi queste ricorrenza?
T(n) = 2T([N/2]) + N
Grazie mille
mi sto preparando per l'esame di algoritmi e
non riesco a capire come risolvere le ricorrenze con il metodo di sostituzione..
per esempio mi potete spiegare senza saltare i passi queste ricorrenza?
T(n) = 2T([N/2]) + N
Grazie mille
Risposte
Ciao,
vedi un po' qusta discussione, si parla del metodo di sostituzione (o per tentativi).
La parte intera di $n/2$ è floor o ceil? Comunque prova ad applicare ciò che è scritto con tipo $O(nlogn)$, se avrai problemi posta pure i tuoi dubbi.
vedi un po' qusta discussione, si parla del metodo di sostituzione (o per tentativi).
La parte intera di $n/2$ è floor o ceil? Comunque prova ad applicare ciò che è scritto con tipo $O(nlogn)$, se avrai problemi posta pure i tuoi dubbi.
grazie mille per la risposta... 
ho letto un po di cose e ho capito che mi sa ho qualche lacuna in matematica..
bisogna dimostrare che T(n) <= cn lg n
supponendo che il limite sia valido per n/2 quindi
T(n/2) <= c[n/2] lg[n/2] quindi facendo la sostituzione
T(n) <= 2(c[n/2] lg([n/2])) + n
adesso come si prosegue?
ho letto un po di cose e ho capito che mi sa ho qualche lacuna in matematica..
bisogna dimostrare che T(n) <= cn lg n
supponendo che il limite sia valido per n/2 quindi
T(n/2) <= c[n/2] lg[n/2] quindi facendo la sostituzione
T(n) <= 2(c[n/2] lg([n/2])) + n
adesso come si prosegue?
Ciao,
ok tieni conto che è una dimostrazione per induzione un po' particolare, se non ricordi quella generale vedi queso sunto (scritto da apatriarca).
cmq non mi hai risposto: la parte intera è $\lfloor n/2 \rfloor$ (floor) oppure \(\lceil \frac n 2 \rceil\) (ceil)? cambia la dimostrazione se è un caso o l'altro...
ok tieni conto che è una dimostrazione per induzione un po' particolare, se non ricordi quella generale vedi queso sunto (scritto da apatriarca).
cmq non mi hai risposto: la parte intera è $\lfloor n/2 \rfloor$ (floor) oppure \(\lceil \frac n 2 \rceil\) (ceil)? cambia la dimostrazione se è un caso o l'altro...
è floor
vediamo allora...
aggiungendo le formule:
\[T(n) \leq 2c \lfloor \frac{n}2 \rfloor log_2(\lfloor\frac{n}2 \rfloor) + n\]
\[\leq 2c \frac{n}2 log_2(\frac{n}2) + n\] per \(\lfloor \frac{n}2 \rfloor \leq \frac{n}2 < \lfloor \frac{n}2 \rfloor +1\)
\[= cn(log_2(n) - 1) + n = cnlog_2(n) - cn + n \leq cnlog_2(n) \rightarrow c\geq1\]
manca il caso base ed hai dimostrato che $T(n) in O(nlog_2(n))$, semplice
PS: sai di che famoso algoritmo è la funzione di ricorrenza?
edit:
corretto errore.
"oxidojack":
bisogna dimostrare che T(n) <= cn lg n
supponendo che il limite sia valido per n/2 quindi
T(n/2) <= c[n/2] lg[n/2] quindi facendo la sostituzione
T(n) <= 2(c[n/2] lg([n/2])) + n
adesso come si prosegue?
aggiungendo le formule:
\[T(n) \leq 2c \lfloor \frac{n}2 \rfloor log_2(\lfloor\frac{n}2 \rfloor) + n\]
\[\leq 2c \frac{n}2 log_2(\frac{n}2) + n\] per \(\lfloor \frac{n}2 \rfloor \leq \frac{n}2 < \lfloor \frac{n}2 \rfloor +1\)
\[= cn(log_2(n) - 1) + n = cnlog_2(n) - cn + n \leq cnlog_2(n) \rightarrow c\geq1\]
manca il caso base ed hai dimostrato che $T(n) in O(nlog_2(n))$, semplice
PS: sai di che famoso algoritmo è la funzione di ricorrenza?
edit:
corretto errore.
"hamming_burst":
manca il caso base ed hai dimostrato che $T(n) in O(nlog_2(n))$, semplice
PS: sai di che famoso algoritmo è la funzione di ricorrenza?
E' il MergeSort?
O(1) se n = 1 è il caso base?
Oddio queste ricorrenze sono acidelle.....
"Giova411":
[quote="hamming_burst"]
manca il caso base ed hai dimostrato che $T(n) in O(nlog_2(n))$, semplice
PS: sai di che famoso algoritmo è la funzione di ricorrenza?
E' il MergeSort?
[/quote]
sembra che intendessi quello. Ma in realtà solo la ricorrenza generale $T(n)=2T(n2)+n$ è più simile a quella reale del Margesort che è $T(n)=T(⌊n2⌋)+T(⌈n2⌉)+Θ(n)$.
o forse intendevo altro, non ricordo...
$O(1)$ se $n = 1$ è il caso base?
dipende. Se intendi un valore generico fissato nella definizione della ricorrenza, per valori piccoli di n, allora sì.
Se intedi il caso base della dimostrazione induttiva sopra riporta, allora...prova a finire la dimostrazione e vedrai il giochetto.
Oddio queste ricorrenze sono acidelle.....
solo in parte, una volta che hai fatto qualche esercizio vedrai ad occhio dove stanno i problemi.
Ti ringrazio tantissimo!!
"hamming_burst":
Se intedi il caso base della dimostrazione induttiva sopra riporta, allora...prova a finire la dimostrazione e vedrai il giochetto.
HamminG altro che giochetto...
Dici di finire per bene matematicamente?
T(1)? e T(0)?
[Perdona la lentezza, pensavo d'aver capito in un primo momento...]
Avevo provato a ragionare:
\( T(n) = 2T(\frac{n}{2}) + n \)
\( T(n) = 4T(\frac{n}{4}) + 2n \)
\( T(n) = 8T(\frac{n}{8}) + 3n \)
Non so che fare poi.
Se \( n = 0\) ho \( T(0) = 0 \)
mi pare di andare a caso...
Ma sto mischiando le cose sicuro...
Forse basta vedere cosa succede per \( c = 0 \) visto che avevi trovato cosa succede per \( c>1 \)
\( T(n) = 2T(\frac{n}{2}) + n \)
\( T(n) = 4T(\frac{n}{4}) + 2n \)
\( T(n) = 8T(\frac{n}{8}) + 3n \)
Non so che fare poi.
Se \( n = 0\) ho \( T(0) = 0 \)
mi pare di andare a caso...
Ma sto mischiando le cose sicuro...Forse basta vedere cosa succede per \( c = 0 \) visto che avevi trovato cosa succede per \( c>1 \)
aspetta, non capisco che stai facendo.
Vuoi dimostrare ed utilizzare cosa?
Io ti avevo proposto di finire la dimostrazione della ricorrenza dell'OP, cioè: $2T(\lfloor n/2 \rfloor) + n$, in questo caso abbiamo (ho) dimostrato che è $O(nlog_2(n))$, manca solo il caso base che è un pochetto più difficile del solito; è lì il "giochetto".
se vuoi calcolare altro, cioè la ricorrenza $2T(n/2) + n$ con il metodo iterativo, basta dirlo e vediamo.
Vuoi dimostrare ed utilizzare cosa?
Io ti avevo proposto di finire la dimostrazione della ricorrenza dell'OP, cioè: $2T(\lfloor n/2 \rfloor) + n$, in questo caso abbiamo (ho) dimostrato che è $O(nlog_2(n))$, manca solo il caso base che è un pochetto più difficile del solito; è lì il "giochetto".
se vuoi calcolare altro, cioè la ricorrenza $2T(n/2) + n$ con il metodo iterativo, basta dirlo e vediamo.
Hihihi Mo mi mandi a quel paese e ti darei ragione!!
Sì ok sono due metodi diversi e non sono riuscito ad arrivare a nulla...
Studiando la teoria mi perdo, credimi!
Metodo per sostituzione manca "il giochetto" che non
Metodo per iterazione lo sto iniziando a capire da oggi... (forse
)
Sì ok sono due metodi diversi e non sono riuscito ad arrivare a nulla...
Studiando la teoria mi perdo, credimi!
Metodo per sostituzione manca "il giochetto" che non
Metodo per iterazione lo sto iniziando a capire da oggi... (forse
)
Aiutoooooo 
L'induzione su n forse da più casi base, non solo uno...
Io non ce la faccio a dire che questo esercizio è concluso in modo esaustivo...
Non lo capisco il giochetto, posso starci ore ed ore..
L'induzione su n forse da più casi base, non solo uno...
Io non ce la faccio a dire che questo esercizio è concluso in modo esaustivo...
Non lo capisco il giochetto, posso starci ore ed ore..
Metto dove mi ero "buttato"...
Con n=1 T(1) non è inferiore a cio' che vogliamo.
Con n=2 T(2) rispetta la proprietà con un c >= 2
Poi cosa bisogna fare?
Con n=1 T(1) non è inferiore a cio' che vogliamo.
Con n=2 T(2) rispetta la proprietà con un c >= 2
Poi cosa bisogna fare?
Il giochetto forse l'ho capito...
Così per dire di concludere il forum in oggetto.
Cioé che possiamo scegliere il caso base che vogliamo.
n=2, n=3 etc etc
Spero che qualcuno confermi
Così per dire di concludere il forum in oggetto.
Cioé che possiamo scegliere il caso base che vogliamo.
n=2, n=3 etc etc
Spero che qualcuno confermi
"Giova411":
Il giochetto forse l'ho capito...
Cioé che possiamo scegliere il caso base che vogliamo.
n=2, n=3 etc etc
:
esatto.
continuando con la dimostrazione, abbiamo fatto il passo induttivo per $T(n) = 2T(\lfloor n/2 \rfloor) + n$
Manca il passo base.
\[\displaystyle{T(n) = 1 \nleq c * 1 \log_2(1) = 0}\]
che è quindi falso. Il giochetto, come hai compreso, sta nel dedurre e capire che siamo in notazione asintotica e possiamo spostare e scegliere il valore inziale $n$, e di validità della ricorrenza, a piacere (ovviamente, con cognizione di causa).
Dunque, avanti:
$T(2) = 2T(\lfloor 1 \rfloor) + 2 = 4 \leq c*2\log_2(2) -> c >= 2$
$T(3) = 2T(\lfloor 1 \rfloor) + 3 = 5 \leq c*3\log_2(3) -> c > 1.051$
$T(4) = 2T(\lfloor 2 \rfloor) + 4$
con l'ultima ricorrenza possiamo utilizzare la definizione della ricorrenza per $n>1$, ridefinendo il tutto secondo la dimostrazione.
::::::::::::::::::::::::::::::::::::::::::::::::::::::
Per $2T(n/2) + n$ con metodo iterativo:
"Giova411":
Avevo provato a ragionare:
\( T(n) = 2T(\frac{n}{2}) + n \)
\( T(n) = 4T(\frac{n}{4}) + 2n \)
\( T(n) = 8T(\frac{n}{8}) + 3n \)
Non so che fare poi.
Se \( n = 0 \) ho \( T(0) = 0 \)
mi pare di andare a caso...
Forse basta vedere cosa succede per \( c = 0 \) visto che avevi trovato cosa succede per \( c>1 \)
stai mischiando le metodologie.
Il metodo con sostituzione prevede di ipotizzare una classe di complessità e dimostrare per induzione sulla ricorrenza.
Il metodo iterativo (il metodo ad albero, et all) prevede di calcolare algebricamente (e simili) una complessità (un ordine di grandezza) ed in secondo piano utilizzare l'induzione per certificarne l'appartenenza. L'utilizzo dei casi base avviene solo se parti a calcolare la ricorrenza da $T(0)$ e non da $T(n)$, diciamo visione bottom up e top down; io preferisco la seconda.
$T(n) = 2T(n/2) + n = 2(2T(n/2^2) + n/2) + n = 2(2(2T(n/2^3) + n/2^2) + n/2) + n =$
$... = 2^mT(n/2^m) + sum_{k=0}^{m-1} 2^kn/2^k = ... =$
$... = 2^mT(1) + n*m = 2^m*c + n*m$ con $T(1) \in O(1)$ che è costante $c$.
mi segui? ho lasciato qualche passaggio per ovvietà. Ne manca ancora uno per arrivare alla classe di complessità, è una sostituzione. Se immagini la ricorrenza come una serie di passaggi e ramificazioni, ed altresì al Marge sort ed alla sua rappresentazione astratta capirai di cosa parlo.
se hai domande basta scriverle.
Mastodontico!!!
Tutto chiarissimo!!!
Tutto chiarissimo!!!
"hamming_burst":
...siamo in notazione asintotica e possiamo spostare e scegliere il valore inziale $n$, e di validità della ricorrenza, a piacere.
E' questa la cosa che sto digerendo piano piano...
grazie mille!
giovanni
"hamming_burst":
se hai domande basta scriverle.
Sì HB ho domande...
Più vado avanti, purtroppo molto lentamente, e... più vado indietro!!!
In un primo momento, quando esultavo impulsivamente, capivo di dover sostituire semplicemente \[ m= log_2n \]
Ecco che ho chiuso contento etc etc ma anche perché forzavo la mano ad occhi chiusi sapendo di dover arrivare ad $ n * log_2n $ In questo caso sarebbe stato $n + n * log_2n $ e tralascio il primo $n$ insignificante.
Tutto cio' perché avevo intravisto che si potevano semplificare i due $ 2^k $ nella sommatoria.
Poi però mi è presa una certa insicurezza: ho finito qui?
E riguardando indietro mi son pure fatto una domanda idiota
"hamming_burst":Poteva anche essere $ c>=1$ ?
\[...\rightarrow c>1\]
"Giova411":
In questo caso sarebbe stato $n + n * log_2n $ e tralascio il primo $n$ insignificante.
Tutto cio' perché avevo intravisto che si potevano semplificare i due $ 2^k $ nella sommatoria.
ok.
chiarificando: devi valutare la ricorrenza in $T(1)$, astrattamente vedere quanti "passi" o livelli ha la ricorrenza per arrivare al caso base cioè a $T(1)$.
sottolineo che si usa la proprietà algebrica: $a^{\log_b(n)} = n^{\log_b(a)}$
$n/2^m = 1$ con $m=\log_2(n)$ perchè: $n/2^{\log_2(n)} = n/n = 1$
quindi $2^m T(1) + sum_{k=0}^{m-1}n = 2^{\log_2(n)} + sum_{k=1}^{\log_2(n)}n = n + n*log_2(n) \in O(n*log_2(n))$
"Giova411":Poteva anche essere $ c>=1$ ?[/quote]
E riguardando indietro mi son pure fatto una domanda idiota [quote="hamming_burst"]
\[...\rightarrow c>1\]
certo, direi che hai ragione. correggo, grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo