[C++] Calcolo della relazione di ricorrenza

[Gianni91]

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

[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;

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]

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..

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
Potresti esternare il tuo ragionamento magari mi é piu chiaro come ragionarci..

[ramy89]

La soluzione giusta è T(n)=cn^2+T(n/2).
Ma cosa intendi per "esternare il tuo ragionamento"?

[Gianni91]

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]

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]

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)

[ramy89]

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]

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