PDA

Visualizza la versione completa : [C++] Calcolo della relazione di ricorrenza


Gianni91
18-01-2012, 17:27
Ragazzi vorrei dei chiarimenti sul come ricavare la relazione di ricorrenza di un algoritmo..
Ecco la funzione con il mio ragionamento.


int g(int x){
if(x<=0)return 1;-->c
int a=0;----->b
for(int i=0;i<= x*x;i++)
a+=i; --->n^2+n^2
return a+g(x/2);--->b
}
Altra domanda riguarda un chiarimento io,ho due soluzioni ..
T(n)=cn^2+T(n/2);
R(n)=cn^4+R(n/2);
Qual'è la differenza??Potreste spiegarmi il ragionamento per il calcolo della relazione di ricorrenza..
Grazie :ciauz:

ramy89
18-01-2012, 17:45
Niente, era R(n) = cn^4+R(n/2) se il for era scritto così:


for(int i=0;i<= x*x*x*x;i++)
a+=i;

Questo semplicemente perchè il for viene eseguito x^4 volte.
Quello che devi fare per calcolare una relazione di ricorrenza è esaminare tutti i possibili casi (es: per quale valore termina la funzione? cosa succede se n ha un determinato valore?).In una funzione come questa i casi sono due: n<=0 e n>0.
Poi assegni i costi alle singole operazioni.Puoi anche a meno di assegnare il costo di un ciclo for, puoi assegnare il costo semplicemente al corpo del for.
Poi vedi quante volte viene eseguita quella singola istruzione a cui hai assegnato il costo.Se la funzione è ricorsiva aggiungi anche il costo della chiamata ricorsiva.
Esempio:


int f(int x)
{
if(x==0)
return 1;
else
{
int sum=0;
for(int i=0;i<x;i++)
sum+=i;
return sum+f(x/2);
}
}

Allora assegnando un costo costante al corpo del for che chiamo c, distingui due casi:
T(f(x))=1 se x=0
T(f(x))=xc+T(x/2) se x>1
E dalla relazione di ricorrenza sei in grado di calcolarti la complessità.

Gianni91
18-01-2012, 17:59
Originariamente inviato da ramy89
Niente, era R(n) = cn^4+R(n/2) se il for era scritto così:


for(int i=0;i<= x*x*x*x;i++)
a+=i;


Ma se ho un risultato diverso vuol dire che va calcolato in un'altro modo.. :confused:


Esempio:


int f(int x)
{
if(x==0)
return 1;
else
{
int sum=0;
for(int i=0;i<x;i++)
sum+=i;
return sum+f(x/2);
}
}


Allora assegnando un costo costante al corpo del for che chiamo c, distingui due casi:
T(f(x))=1 se x=0
T(f(x))=xc+T(x/2) se x>1
E dalla relazione di ricorrenza sei in grado di calcolarti la complessità.
Ci sono quasi pienamento nel tuo ragionamento :D
Potresti esternare il tuo ragionamento magari mi é piu chiaro come ragionarci..

ramy89
18-01-2012, 18:13
La soluzione giusta è T(n)=cn^2+T(n/2).
Ma cosa intendi per "esternare il tuo ragionamento"?

Gianni91
18-01-2012, 18:35
scusami magari mi sono spiegato male,
Intendevo che R(n) se ha un risultato diverso ,vuol dire che si ricava in qualche altro modo e sopratutto cosa é???'
Esternare il tuo ragionamento intendevo se non ti scoccia, dirmi piu procesamente come ragioni in modo da capire proprio come analizzare gli algoritmi..

ramy89
18-01-2012, 19:12
Se la relazione di riccorrenza è diversa vuol dire che è la relazione di ricorrenza di un altro algoritmo.Si ricava proprio da un altro algortimo, che è diverso.
Io ragiono così: prima di tutto assegno un costo a qualsiasi blocco di codice.
Poi mi chiedo quante volte viene eseguito quel blocco in ogni singola chiamata, qual'è la chiamata ricorsiva e qual'è la clausola di chiusura, cioè di temrinazione dell' algoritmo.Rispondendo a queste tre domande so ricavarmi la formula di ricorrenza.
Sempre nell' esempio che ho fatto della f(x), ragiono così:
Assegno un costo c all' istruzione sum+=i;
Rispondo alla rpima domanda: il blocco viene eseguito x volte.
Rispondo alla seconda domanda: la chiamata ricorsiva è f(x/2), per cui al costo di una singola chiamata ci aggiungo questo costo.Rispondo alla terza domanda: l' algoritmo termina quando x=0.
Per cui posso stabilire che il costo è:
- 1 se x=0;
- nc + t(x/2) se x>0.
Ora bisogna calcolare il costo effettivo di una generica chiamata a f(x) passandogli come parametro un valore generico.
Dovrebbe venire (cn^2)/2 se non mi sbaglio.

Gianni91
18-01-2012, 19:26
Originariamente inviato da ramy89
Se la relazione di riccorrenza è diversa vuol dire che è la relazione di ricorrenza di un altro algoritmo.Si ricava proprio da un altro algortimo, che è diverso.

Guarda non ne sono tanto sicuro e poi perchè chiamarlo in modo diverso??
Ti linko la traccia cosi si capisce meglio
Testo(esercizio 3) (http://info.iet.unipi.it/~fondii/Esami/Materiale/Algoritmi-2011-02-25.pdf)

ramy89
18-01-2012, 20:28
Senti non mi linkare le tue dispense che ti danno all' università, ci mancherebbe solo che mi metto a studiare sulle tue dispense.
Ogni algoritmo per un dato input ha una sua complessità computazionale, com'è possibile che ne abbia due?
Cioè dovrebbe essere vero sia che la complessità è n^2, ma anche che è n^4?
Si vede dal codice che la complessità è n^2, semmai il risultato della funzione,cioè il valore restituito dalla funzione è O(n^4), ed esattamente (N^4)/2.

Gianni91
18-01-2012, 21:19
vb,era solo una traccia per farti vedere di cosa parlavo ,mica la mia dispensa....
Cmq probabilemente R(n) ,sarà la complessità del risultato..
Grazie

Loading