Impostare Equazioni di Ricorrenza

[idroir]

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:

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?

[apatriarca]

Il primo passaggio è corretto. Per \(T_p\) devi semplicemente osservare che viene eseguito una sola volta e che è costituito da un ciclo che viene eseguito \(a\) volte e il cui corpo ha complessità costante. Sarà quindi qualcosa come \(T_p = c_{p1} + n\,c_{p2}.\) Siccome solo la complessità asintotica ti interessa possiamo semplificare a \(T_p = n\).

Per quanto riguarda \(T_q,\) osserviamo prima di tutto che \(q\) è una funzione ricorsiva che ha costo costante quando \(i \geq j\). Negli altri casi abbiamo (tralasciando parti di costo costante)
\[ T_q(i, j) = T_q\bigl(i, i + d\bigr) + T_q(i + d + 1, i + 2\,d) + T_q(i+2\,d + 1, j). \]
Scrivo per prima cosa \(j = i + 3\,d\) ottenendo quindi:
\[ T_q(i, i + 3\,d) = T_q\bigl(i, i + d\bigr) + T_q(i + d + 1, i + 2\,d) + T_q(i+2\,d + 1, i+3\,d). \]
Osservo a questo punto che la complessità non dipende dal valore scelto per \(i,\) ma solo dalla differenza tra i due valori in input. Per cui posso semplicemente scrivere:
\[ T_q(n) = T_q(3\,d) = T_q(d) + 2\,T_q(d - 1) \approx 3\,T_q(d). \]
Questa relazione implica che il tempo sarà di nuovo lineare e quindi anche \(T_r\) lo sarà..

[idroir]

Grazie per la risposta, avrei bisogno di un paio di chiarimenti.

Da dove deriva che $ j=i+3d $ ?
E nella formula \[ T_q(n) = T_q(3\,d) = T_q(d) + 2\,T_q(d - 1) \approx 3\,T_q(d). \] da dove viene $ 2T_q(d-1) $ ?

Le equazioni di ricorrenza non le hai proprio utilizzate perchè la complessità non dipende dalla dimensione dell'input?

Grazie!!

[apatriarca]

Ho definito \(T_q(x) = T_q(0, x)\) e siccome \(T_q(s, s + x) = T_q(0, x) = T_q(x)\) ho semplificato sia \(T_q(i + d + 1, i + 2d)\) che \(T_q(i + 2\,d + 1, i + 3\,d)\) a \(T_q(d - 1)\).

[apatriarca]

Dalla formula
\[ d = (j - i)/3 \implies j = i + 3\,d. \]
Ovviamente la formula vale solo nel caso in cui \(j - i\) sia effettivamente divisibile per \(3\), ma quando si fanno calcoli asintotici non ha più di tanto importanza. L'errore ottenuto è molto piccolo in rapporto ad \(n\). In particolare hai che \(i + 3\,d \leq j < i + 3\,(d + 1)\) per cui volendo puoi scrivere \( T_q(i, j) = T_q(i, i + 3\,d + C) \) e poi il resto sarebbe uguale tranne che per l'ultimo fattore. Alla fine arriveresti comunque a
\[T_q(d) + T_q(d-1) + T_q(d-1+C) \approx 3\,T_q(d) \quad (0 \leq C < 3). \]

[idroir]

ok, perfetto, ora ho capito, è il primo esercizio che faccio di questo tipo, per caso sapresti aiutarmi anche per il punto b cioè:

 Determinare il costo spaziale asintotico dell’algoritmo descritto da r(int) in funzione della dimensione
dell’input.