Problema con equazione di ricorrenza

[Manugal]

Ciao a tutti

Sto cercando di risolvere questa equazione di ricorrenza. L'algoritmo di cui ne devo analizzare la complessità è il seguente:

int Run (int A[], int n){
   if(n >= 199){
      int m=(3*n)/4;
      return (Run(A,m) || Run(A + n - m, m) ? 1 : 0);
   } else {
   int v = A[n/2], c = 0, k;
   for (k = n/2 ; k >=0 && A[k] == v ; k--) c++;
   for (k = n/2 + 1 ; k < n && A[k] == v ; k++) c++;
   return (c >= 100 ? 1 : 0);
}

Allora io ho fatto:

Se n < 199:
T(n) = c*n

Se n>=199:
T(n) = 2T(3n/4) + c*n

Usando il metodo iterativo (o l'albero di ricorsione) come la risolvo? Grazie.

[vl4dster]

Se ti interessa solo la complessita' dell'algoritmo,
allora ti dovrebbe interessare l'andamento asintotico di $T(n)$ per $n >= n_0$
dunque puoi benissimo tralasciare il caso $n<199$, diverso e'
il discorso nel caso tu voglia la soluzione esatta della ricorrenza.

Se n>=199:
T(n) = 2T(3n/4) + c*n 

non capisco perche' dici $+ c*n$,
io vedo solo un $+ O(1)$ dovuto
all'istruzione $"int m=(3*n)/4"$.

Detto questo conosco un bellissimo teorema detto
Master Theorem che recita come segue:

Siano $a>=1$, $b>1$ due costanti e $f(n)$ una funzione definita sugli interi positivi.
Sia $T(n) = a T(n/b) + f(n)$. Dove per $n/b$ intendiamo la parte intera (superiore o inferiore e' indifferente).
Allora si hanno tre casi,
caso 1)
Se $f(n) = O(n^{log_b(a) - \epsilon})$, per $epsilon > 0$
allora $T(n) = \Theta(n^{log_b(a)})$

Caso2)
Se $f(n) = \Theta(n^{log_b(a)})$
allora $T(n) = O(lg(n) \cdot n^{log_b(a)})$

Caso 3)
Se $f(n) = \Omega(n^{log_b(a)+\epsilon})$, per $epsilon > 0$
e se $a\cdot f(n/b) <= c\cdot f(n)$ per qualche costante $0 < c < 1$
allora $T(n) = \Theta(f(n))$

La dimostrazione e' lunga, e ancor di piu' noiosa, ma il teoremino
generale fa al tuo caso in quanto risolve automagicamente la ricorrenza
$T(n) = 2T(3n/4) + O(1)$

Prova ad applicarlo da solo, in caso:

$O(1) = O(n^{log_{4/3}(2)})$ dunque per il teoremone, caso 1) si ha
$T(n) = \Theta(n^{log_{4/3}(2)})$

edit:corretto un typo

[Manugal]

Grazie per la risposta. Allora ho scritto c*n perché quello è il costo di quel ciclo che sta nel ramo else.

Per quanto riguarda il Master Theorem lo conosco, solo che avrei voluto vedere la soluzione iterativa (o con l'albero di ricorrenza), infatti provandoci ho visto che è un po' intricata.

Comunque seguendo il Master Theorem:

a=2 b=4/3 e f(n)=O(1) (b è uguale a 4/3 perché ho visto un esempio sul mio libro dove c'è T(2n/3) e pone b=3/2)

Quindi sono nel Caso 1) dove ho che $f(n)=O(n^{log_b(a)}-ε)$ cioè $f(n)=O(n^{log_{4/3}(2)})$ e quindi $T(n) = Θ(n^{log_{4/3}(2)})$. O sbaglio?

[vl4dster]

esatto , (l'$epsilon$ pero' e' nell'esponente)

[Manugal]

Grazie mille