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?