Newsgroup: it.comp.lang.c
Titolo: Complessità computazionale

Salve a tutti.
Ho il seguente problema. Devo determinare la complessità asintotica, nel
caso
peggiore, del seguente algoritmo:
short DoppioRic(float a[], long p, long u)
{
  if (p == u) return 0;
  else
  {
    long m = (p + u) / 2;
    short r = DoppioRic(a, p, m);
    if (r == 0) r = DoppioRic(a, m+1, u);
    while (r == 0 && p <= m)
    {
      long i = m + 1;
      while (r == 0 && i <= u)
      {
        if (a[p] == a[i]) r = 1;
        else i++;
      }
      p++
    }
    return r;
  }
}
short Doppio(float a[], long n)
{
  return DoppioRic(a, 0, n - 1);
}
Quello che la funzione DoppioRic (chiamata da Doppio) è prendere in
input
un vettore (inizialmente lungo n) e ritornare 1 o 0 a seconda che vi sia
un valore ripetuto almeno due volte.
Io ho ragionato così. Il caso peggiore è quando non vi è nessun elemento
ripetuto all'interno dell'array. Il funzionamento  di Doppio() è
semplice:
- divide in due l'intervallo di numero
- esegue il controllo sul primo intervallo di valori
  (se lo trova, restituisce 1, altrimenti 0 e la ricorsione continua)
- esegue il controllo sul secondo intervallo di valori
  (se lo trova, restituisce 1, altrimenti 0 e la ricorsione continua)
ovviamente, tutto tramite ricorsione. Allora, mi è venuto in mente di
scrivere l'equazione di ricorrenza (simile a quella del merge-sort)
come:
T(n) <= 2*T(n/2) + (n^2)/4
T(1) <= d
Cioè, il tasso asintotico su di un input di n elementi è dato da due
volte quello
su di un input di n/2 elementi più il costo dei due cicli while, che
dovrebbe essere
quadratico (limitato sia sup. che inf.). Infatti, quando si arriva ai
while con
m = (0 + n - 1) / 2, si stanno confrontando le due metà dell'array
originario,
sicuri che quantomeno in entrambe non ci sono ripetizioni. Bisogna
quindi
controllare n/2 elementi contro n/2 elementi, iterando quindi n/2 * n/2
volte,
ovvero (n^2) / 4.
Allora, secondo un famoso teorema (o facendo i calcoli, tramite
sostituzione), si
dovrebbe ottenere che la complessità asintotica è Theta(n^2).
In verità, sarei tentato di sostituire a (n^2)/4 direttamente
Theta(n^2), ottenendo
alla fine lo stesso risultato.
Cosa ne pensate?
Grazie.

 Cosa ne pensate?
e' un bel po' che ho dato quell'esame ( + di 10 anni... sigh ), il 
ragionamento comunque mi sembra filare.
un appunto: trattandosi di limiti per n->oo, O(n^2) e' sicuramente + 
corretto di O((n^2)/4)

 wrotg:

La complessita' sara' dell'ordine di   
c * (n^2)
---------  + K
    4   
che puoi scrivere come:
 c
--- * (n^2) + K
 4
che come insegna la teoria e' semplicemente O(n^2), visto che non sai
quanto vale C e potrebbe benissimo essere maggiore di 4... fai un po'
di test di complessita' sperimentale e pratica comuneque: e' il modo
migliore per provare se i tuoi calcoli sono esatti.
Paolo.
P.S. Non mi sono soffermato a controllare se si potesse anche indicare
come THETA(n^2)

 migliore per provare se i tuoi calcoli sono esatti.
i calcoli li faccio sempre per trovare i possibili bottle-neck, anke se 
non in maniera molto "ortodossa" (a volte ci metto dentro anche cose 
come il task switching in MT e di scheduling in SMP ;), intendevo che 
non saprei spiegare "con tutti i crismi" se il ragionamento, da un 
punto di vista prettamente accademico, fosse corretto.