[Algoritmi] scrivere ricorrenza
ho fatto l'esame di algoritmi ed è uscito un'esercizio in cui andava trovata l'equazione di ricorrenza dfi un'algoritmo.
io ho scritto la seguente equazione di ricorrenza:
T(1) = c
T(n) = 2T(n/2) + O(n)
l'ho risolta con il teorema principale, e come risoltato mi è uscito T(n) = O(nlogn)
l'equazione di ricorrenza è giusta?
sia considerato il seguente algoritmo ricorsivo che conta il numero di punti fissi, ossia il numero di indici tali che v=i, presenti all'interno di un'array.
int Conta( inizio, fine )
{
se (inizio > fine)
return; (fin qui è O(1) )
mediana = ArrotondaPerDifetto((fine+inizio)/2) (qui 2T(n/2) )
se v[mediana] = mediana
fisso=1
else
fisso=0 (l'if e l'else sempre O(1)
fissiSinistra = Conta( inizio, mediana-1)
fissiDestra = Conta( mediana+1, fine)
ritorna = fisso + fissiSinistra + fissiDestra qui ho messo O(n)
}
io ho scritto la seguente equazione di ricorrenza:
T(1) = c
T(n) = 2T(n/2) + O(n)
l'ho risolta con il teorema principale, e come risoltato mi è uscito T(n) = O(nlogn)
l'equazione di ricorrenza è giusta?
Risposte
Ciao,
No, mi dispiace.
Domanda: perchè mai $O(n)$?
Nota1: Situazione uguale di questo, dove ti spiegavo come calcolare l'equazione di un algoritmo divide-et-impera.
Nota2 (pignoleria): per te cos'è "arrotonda per difetto"?
Prova a leggere quel post e a capire il tuo "errore", poi vediamo
l'equazione di ricorrenza è giusta?
No, mi dispiace.
Domanda: perchè mai $O(n)$?
Nota1: Situazione uguale di questo, dove ti spiegavo come calcolare l'equazione di un algoritmo divide-et-impera.
Nota2 (pignoleria): per te cos'è "arrotonda per difetto"?
Prova a leggere quel post e a capire il tuo "errore", poi vediamo
"ham_burst":
Ciao,
l'equazione di ricorrenza è giusta?
No, mi dispiace.
Domanda: perchè mai $O(n)$?
Nota1: Situazione uguale di questo, dove ti spiegavo come calcolare l'equazione di un algoritmo divide-et-impera.
Nota2 (pignoleria): per te cos'è "arrotonda per difetto"?
Prova a leggere quel post e a capire il tuo "errore", poi vediamo
di tutto il programma di algoritmi, scrivere l'equazione di ricorrenza è una delle poche cose che non ho capito bene.
sinceramente l'algoritmo mi ha confuso un pò, arrotondaPerDifetto è costante?
arrotondaPerDifetto ha complessità costante (al pari di una qualsiasi operazione aritmetica. In effetti, quella riga verrebbe implementata con la seguente riga in un qualsiasi linguaggio di programmazione simile al C:
per via del funzionamento della divisione intera*.
* Almeno per gli interi positivi. Ho usato il tipo int perché non tutti i linguaggi di programmazione con sintassi simile a quella del C supportano i tipi senza segno (per esempio Java). Non sapendo che linguaggio di programmazione conosci ho preferito limitarmi al tipo più compatibile.
int mediana = (fine + inizio) / 2;
per via del funzionamento della divisione intera*.
* Almeno per gli interi positivi. Ho usato il tipo int perché non tutti i linguaggi di programmazione con sintassi simile a quella del C supportano i tipi senza segno (per esempio Java). Non sapendo che linguaggio di programmazione conosci ho preferito limitarmi al tipo più compatibile.
fissiSinistra = Conta( inizio, mediana-1)
fissiDestra = Conta( mediana+1, fine)
queste 2 invece hanno complessità n/2 + n/2 (cioè 2T(n/2), giusto?
quindi dall'algoritmo si ottiene: O(1) + O(1) + n/2 + n/2 + O(1)
quindi 2T(n/2) + O(1) ?
fissiDestra = Conta( mediana+1, fine)
queste 2 invece hanno complessità n/2 + n/2 (cioè 2T(n/2), giusto?
quindi dall'algoritmo si ottiene: O(1) + O(1) + n/2 + n/2 + O(1)
quindi 2T(n/2) + O(1) ?
È in effetti 2T(n/2) + O(1), ma è importante distinguere tra dire che qualcosa ha complessità n/2 e dire che ha complessità T(n/2), come è il caso per le due righe che hai scritto.
un volta ottenuta la ricorrenza corretta, cioè
T(1) = c
T(n) = 2T(n/2) + O(1)
dubbio: scrivere "T(1) = c" è corretto?
e poi come va risolta? basta scrivere T(n) = O(n) (soluzione a cui sono arrivato ad occhio)
o si usa qualche metodo?
T(1) = c
T(n) = 2T(n/2) + O(1)
dubbio: scrivere "T(1) = c" è corretto?
e poi come va risolta? basta scrivere T(n) = O(n) (soluzione a cui sono arrivato ad occhio)
o si usa qualche metodo?
nell'altro thread in cui mi si presentava un caso analogo a questo avevo mostrato un metodo che usa il mio testo per risolvere equazioni in questa forma (http://www.matematicamente.it/forum/post559296.html#p559296)
T(1) = 12
T(n) = 7(n/2) + 3
ovvero si pongono le due equazioni uguali a "an+b", con delle sostituazioni si trova prima la b e poi la a.
ma non so se è adatto anche a equazioni di ricorrenza nel formato T(n) = 7(n/2) + O(1).
come dovrei risolverla?
T(1) = 12
T(n) = 7(n/2) + 3
ovvero si pongono le due equazioni uguali a "an+b", con delle sostituazioni si trova prima la b e poi la a.
ma non so se è adatto anche a equazioni di ricorrenza nel formato T(n) = 7(n/2) + O(1).
come dovrei risolverla?
"mathix":
nell'altro thread in cui mi si presentava un caso analogo a questo avevo mostrato un metodo che usa il mio testo per risolvere equazioni in questa forma (http://www.matematicamente.it/forum/post559296.html#p559296)
T(1) = 12
T(n) = 7(n/2) + 3
ovvero si pongono le due equazioni uguali a "an+b", con delle sostituazioni si trova prima la b e poi la a.
ma non so se è adatto anche a equazioni di ricorrenza nel formato T(n) = 7(n/2) + O(1).
come dovrei risolverla?
Ciao,
come detto in quel post non posso dirti nulla sul tuo modo di procedere perchè non lo conosco.
Ma se guardi bene ed estrapoli le costanti: $7(n/2) + O(1) = 7(n/2) + c1$...
per dimostrarlo (oltre il tuo modo) basta usare l'induzione, stando attenti ad utilizzare l'ipotesi corretta, cioè:
non funziona con $O(n)$ ma con un'ipotesi più forte cioè $O(n - b)$ prova
"mathix":
un volta ottenuta la ricorrenza corretta, cioè
T(1) = c
T(n) = 2T(n/2) + O(1)
dubbio: scrivere "T(1) = c" è corretto?
e poi come va risolta? basta scrivere T(n) = O(n) (soluzione a cui sono arrivato ad occhio)
o si usa qualche metodo?
mi trovo ancora una volta a sbattere la testa su questa ricorrenza.
dopo aver studiato meglio volevo chiedervi se ora questa è la soluzione giusta:
aplichiamo il teorema principale
$\a=2, b=2, f(n)=Theta(1) \$
$\n^(log_2 2) = Theta(n^1) \$
confrontando il risultato $\Theta(n)\$ con $\f(n)=Theta(1)\$
troviamo che è il caso 1 del teorema principale
$\ f(n)=Theta(n^(log_b a-epsilon)) \$ quindi $\ T(n)=Theta(n^(log_b a)) \$
la soluzione è $\T(n)=Theta(n)\$ giusto?
Attenzione il Master Theorem nel caso che $f(n) in \Theta(1)$ ha poco senso (o solo in minima parte)
Te utilizzi troppo la notazione $Theta()$, più corretto è dire:
$\Theta(1) in O(n^{log_2(2) - \epsilon})$ con es: $\epsilon=0.5$ perciò $\Theta(1) in O(sqrt(n))$, quindi $T(n) in Theta(n)$.
Gli altri casi non hanno nessun senso logico, ti pare che puoi limitare inferiormente una complessità costante $O(1) in \Omega(n^{1+\epsilon})$, mi pare di no
Ma in questo caso, a mio modo di vedere, è poco utile tutto ciò, esistono altre tecniche apposite.
L'"Attenzione" sta nel fatto che non puoi dimostrare che questa limitazione è corretta, devi usare uno stratagemma come ti ho indicato.
se hai dubbi chiedi pure
Te utilizzi troppo la notazione $Theta()$, più corretto è dire:
$\Theta(1) in O(n^{log_2(2) - \epsilon})$ con es: $\epsilon=0.5$ perciò $\Theta(1) in O(sqrt(n))$, quindi $T(n) in Theta(n)$.
Gli altri casi non hanno nessun senso logico, ti pare che puoi limitare inferiormente una complessità costante $O(1) in \Omega(n^{1+\epsilon})$, mi pare di no
Ma in questo caso, a mio modo di vedere, è poco utile tutto ciò, esistono altre tecniche apposite.
L'"Attenzione" sta nel fatto che non puoi dimostrare che questa limitazione è corretta, devi usare uno stratagemma come ti ho indicato.
se hai dubbi chiedi pure
"hamming_burst":
Attenzione il Master Theorem nel caso che $f(n) in \Theta(1)$ ha poco senso (o solo in minima parte)
Te utilizzi troppo la notazione $Theta()$, più corretto è dire:
$\Theta(1) in O(n^{log_2(2) - \epsilon})$ con es: $\epsilon=0.5$ perciò $\Theta(1) in O(sqrt(n))$, quindi $T(n) in Theta(n)$.
Gli altri casi non hanno nessun senso logico, ti pare che puoi limitare inferiormente una complessità costante $O(1) in \Omega(n^{1+\epsilon})$, mi pare di no
Ma in questo caso, a mio modo di vedere, è poco utile tutto ciò, esistono altre tecniche apposite.
L'"Attenzione" sta nel fatto che non puoi dimostrare che questa limitazione è corretta, devi usare uno stratagemma come ti ho indicato.
se hai dubbi chiedi pure
volevo chiederti una cosa riguardo la epsilon del teorema principale. come si trova il valore epsilon? nell'esempio hai scritto che è 0.5 ma in base a cosa è stato scelto?
da quel poco che ho capito vedendo qualche esercizio è la differenza di grado tra $\n^(log_b a) \$ e $\f(n)\$, o sbaglio?
inoltre nel caso di $\Theta(1)\$ dovremmo usare l'induzione, come consigliato da te qualche post piu dietro, giusto?
"mathix":
volevo chiederti una cosa riguardo la epsilon del teorema principale. come si trova il valore epsilon? nell'esempio hai scritto che è 0.5 ma in base a cosa è stato scelto?
da quel poco che ho capito vedendo qualche esercizio è la differenza di grado tra $\n^(log_b a) \$ e $\f(n)\$, o sbaglio?
esatto, come sai è definito come $\epsilon>0$ (per essere utile, meglio $0 < epsilon <= 1$).
Se ne sceglie uno in base alle funzioni in gioco per far appartenere una funzione in una qualche classe di complessità, in questo caso qulunque valore tra $(0,1)$ andava benissimo.
Se vuoi in questo post ho fatto un mini sunto sulle differenze tra i vari metodi e cosa comporta l'utilizzo del Master.
inoltre nel caso di $\Theta(1)\$ dovremmo usare l'induzione, come consigliato da te qualche post piu dietro, giusto?
Nessuno ci vieta di utilizzare il Master per capire a che classe di complessità approssimativamente appartiene una ricorrenza (con suddivisione), ma poi formalmente sarebbe il caso di vedere se effettivamente tale complessità è corretta.
Nel caso di di $f(n) in O(1)$ non arrivi da nessuna parte con l'induzione per questo esiste quel "trucco" (un'ipotesi più forte), ma è pura formalità per dire che non è effettivamente $O(n)$ la sua limitazione stretta: ma per calzare a pennello sarebbe $O(n-b)$, ma come ben sai $O(n-b) in O(n)$.
tutto questo per dire: ok, utilizza pure il master, ma sappi cosa ci sta sotto.
sei stato chiarissimo, ti ringrazio per tutto l'aiuto
risolvendo con il metodo iterativo è venuto fuori $\2n-1\$
ho un'ultima domanda:
se dall'algoritmo del primo post di questo thread io ricavo $\T(n) = 2T(n/2) + O(1)\$
quando devo risolver l'equazione la scrivo come $\T(n) = 2T(n/2) + 1\$
oppure $\T(n) = 2T(n/2) + c \$ ???
e nel caso di $\T(n) = 2T(n/2) + c \$ quando svolgo le iterazioni, le svolgo lasciando la c o per convenzione metto 1 al posto di c?
ho un'ultima domanda:
se dall'algoritmo del primo post di questo thread io ricavo $\T(n) = 2T(n/2) + O(1)\$
quando devo risolver l'equazione la scrivo come $\T(n) = 2T(n/2) + 1\$
oppure $\T(n) = 2T(n/2) + c \$ ???
e nel caso di $\T(n) = 2T(n/2) + c \$ quando svolgo le iterazioni, le svolgo lasciando la c o per convenzione metto 1 al posto di c?
inoltre potresti dirmi se i passaggi di questo esercizio (in particolare la sommatoria) sono giusti?
in questo lascio c al posto di O(1)
$\T(n) = 3T(n/3) + c\$
uso il metodo iterativo:
$\= 3(3T(n/3) + c)+c\$
$\= 3(3(3T(n/3) + c)+c)+c\$
$\= 27T(n/27) +9c + 3c + c\$
$\= 3^kT(n/(3^k)) + c sum_{i=0}^(k-1) 3^i \$ abbiamo che $\ n=3^k\$ e $\k=log_3 n\$
$\= c sum_{i=0}^(log_3 n) 3^i = c(1-3^(log_3 n+1))/(1-3) = c(1-3*3^(log_3 n))/(-2) = c((3n -1)/2) => O(n) \$
la sommatoria nell'ultimo rigo dovrebbe andare da 0 a $\log_3 n\$ o da 0 a $\log_3 n-1\$ ?
in questo lascio c al posto di O(1)
$\T(n) = 3T(n/3) + c\$
uso il metodo iterativo:
$\= 3(3T(n/3) + c)+c\$
$\= 3(3(3T(n/3) + c)+c)+c\$
$\= 27T(n/27) +9c + 3c + c\$
$\= 3^kT(n/(3^k)) + c sum_{i=0}^(k-1) 3^i \$ abbiamo che $\ n=3^k\$ e $\k=log_3 n\$
$\= c sum_{i=0}^(log_3 n) 3^i = c(1-3^(log_3 n+1))/(1-3) = c(1-3*3^(log_3 n))/(-2) = c((3n -1)/2) => O(n) \$
la sommatoria nell'ultimo rigo dovrebbe andare da 0 a $\log_3 n\$ o da 0 a $\log_3 n-1\$ ?
"mathix":
quando svolgo le iterazioni, le svolgo lasciando la c o per convenzione metto 1 al posto di c?
pensaci un momento, cosa rappresenta $O(1)$?
poi ti domando che differenza ci sta tra $O(1)$, $Theta(1)$ e $Omega(1)$.
Se prendessi $O(5)$ invece?
"mathix":
inoltre potresti dirmi se i passaggi di questo esercizio (in particolare la sommatoria) sono giusti?
in questo lascio c al posto di O(1)
$\T(n) = 3T(n/3) + c\$
uso il metodo iterativo:
$\= 3(3T(n/3) + c)+c\$
$\= 3(3(3T(n/3) + c)+c)+c\$
$\= 27T(n/27) +9c + 3c + c\$
$\= 3^kT(n/(3^k)) + c sum_{i=0}^(k-1) 3^i \$ abbiamo che $\ n=3^k\$ e $\k=log_3 n\$
$\= c sum_{i=0}^(log_3 n) 3^i = c(1-3^(log_3 n+1))/(1-3) = c(1-3*3^(log_3 n))/(-2) = c((3n -1)/2) => O(n) \$
la sommatoria nell'ultimo rigo dovrebbe andare da 0 a $\log_3 n\$ o da 0 a $\log_3 n-1\$ ?
ottimo
mi fa piacere hai fatto il procedimento in modo corretto.
Comunque come hai notato ci sono delle piccole inesattezze. Anche se in questo caso specifico non ha un valore molto alto questo che ti dirò, ma tienilo come caso generale, dato che la funzione libera è $O(1)$.
Mettiamo che a quando $n=1$ il costo è costante (anche se è sempre costante). (*)
Si arriva fino a prima del caso base, cioè tipo se il caso base è a livello $h$ non ci fermiamo a $h-1$ cioè in questo caso $log_3(n)-1$.
Poi però dobbiamo ricordarci che esiste un caso base e dobbiamo sommarlo SEPARATAMENTE, cioè ci sarà un $3^{log_3(n)}$ (*) per il caso base.
In sintesi diverrà:
\[(c*\sum_{i=0}^{log_3(n)-1} 3^i) + (3^{log_3(n)})\]
se hai dubbi chiedi pure
"hamming_burst":
[quote="mathix"]quando svolgo le iterazioni, le svolgo lasciando la c o per convenzione metto 1 al posto di c?
pensaci un momento, cosa rappresenta $O(1)$?
poi ti domando che differenza ci sta tra $O(1)$, $Theta(1)$ e $Omega(1)$.
Se prendessi $O(5)$ invece?
[/quote]
L'algoritmo di questa ricorrenza era composto da una suddivisione del problema in 3 parti 3T(n/3) e 3 operazioni di complessità costante, quindi $\T(n) = 3T(n/3) + O(1) + O(1) + O(1) \$
alla domanda su che differenza c'è tra $\O(1), Theta(1), Omega(1)\$ non so rispondere
"hamming_burst":
ottimo
mi fa piacere hai fatto il procedimento in modo corretto.
Comunque come hai notato ci sono delle piccole inesattezze. Anche se in questo caso specifico non ha un valore molto alto questo che ti dirò, ma tienilo come caso generale, dato che la funzione libera è $O(1)$.
Mettiamo che a quando $n=1$ il costo è costante (anche se è sempre costante). (*)
Si arriva fino a prima del caso base, cioè tipo se il caso base è a livello $h$ non ci fermiamo a $h-1$ cioè in questo caso $log_3(n)-1$.
Poi però dobbiamo ricordarci che esiste un caso base e dobbiamo sommarlo SEPARATAMENTE, cioè ci sarà un $3^{log_3(n)}$ (*) per il caso base.
In sintesi diverrà:
\[(c*\sum_{i=0}^{log_3(n)-1} 3^i) + (3^{log_3(n)})\]
se hai dubbi chiedi pure
quindi l'ultimo passaggio dovrebbe essere cosi?
$\= c sum_{i=0}^(log_3 n-1) 3^i + 3^(log_3 n) = c((1-3^(log_3 n))/(1-3)) + 3^(log_3 n) = c((1-n)/(-2)) + n = c((n -1)/2) + n => O(n) \$
"mathix":
L'algoritmo di questa ricorrenza era composto da una suddivisione del problema in 3 parti 3T(n/3) e 3 operazioni di complessità costante, quindi $\T(n) = 3T(n/3) + O(1) + O(1) + O(1) \$
ok è complessità costante.
Una costante la notiamo come $c$, $d$ una lettera che rappresenta una classe di complessità costante.
La notazione con $1$ è una semplice notazione. Puoi scrivere $O(5)$ se ti piace di più, ma con $1$ hai il vantaggio di non dover pensare al valore effettivo dell'algoritmo.
Poi se vai a studiare questa notazione, scopri che esiste la solita costante nascosta $f(n) <= c*1$ dove rappresenta anche il $5$ di prima. con $f(n)$ funzione costante.
alla domanda su che differenza c'è tra $\O(1), Theta(1), Omega(1)\$ non so rispondere
questo lo lascio a te, se hai compreso ciò che ho scritto sopra saprai rispondermi
mi sembra corretta.
F(n) è cmq costante.
tiene presente che il teorema master va usata per algoritimi che usano la ricorsione.
F(n) è cmq costante.
tiene presente che il teorema master va usata per algoritimi che usano la ricorsione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo