Impostare Equazioni di Ricorrenza
Inviato: 30/08/2018, 15:53
Buonasera,
sto riscontrando delle difficoltà ad impostare le Equazioni di ricorrenza, per il calcolo del costo temporale asintotico di un algoritmo ricorsivo.
Prendiamo ad esempio questo problema:
$ T_r=c_1+T_p+T_q $ e quindi poi devo andare a calcolare i tempi di p(int a) che non è ricorsivo, q(int a[]) e q(int a[], int i, int j) fino a qui, vado bene?
Poi come procedo?
sto riscontrando delle difficoltà ad impostare le Equazioni di ricorrenza, per il calcolo del costo temporale asintotico di un algoritmo ricorsivo.
Prendiamo ad esempio questo problema:
- Codice:
Si considerino i metodi Java di seguito illustrati.
static int[] p(int a) {
int arr[] = new int[a]; // assumere O(1)
for(int i = 0; i < a; i++)
arr[i] = i+1;
return arr;
}
static int q(int a[]) {
return q(a, 0, a.length-1);
}
static int q(int a[], int i, int j) {
if(i > j) return 0;
if(i == j) return a[i];
int d = (j-i)/3;
return q(a,i,i+d)+q(a,i+d+1,i+2*d)+q(a,i+2*d+1,j);
}
static int r(int a) {
return q(p(a));
}
Sviluppare quanto segue:
(a) Determinare il costo temporale asintotico dell’algoritmo descritto da r(int) in funzione della dimensione
dell’input.
(b) Determinare il costo spaziale asintotico dell’algoritmo descritto da r(int) in funzione della dimensione
dell’input.
$ T_r=c_1+T_p+T_q $ e quindi poi devo andare a calcolare i tempi di p(int a) che non è ricorsivo, q(int a[]) e q(int a[], int i, int j) fino a qui, vado bene?
Poi come procedo?