C - complessità algoritmi

[gabama]

Buonasera,mi sono trovato a ragionare su questi 2 algoritmi e vorrei delle conferme,se possibile,sulla complessità

int fun(int a[], int n) {
int i;
if(n<2) return a[0];
for(i=1;i<n;i++)
a[i] = a[i]-a[i-1];
return fun(a,1) + fun(a,n-1);
}

sarebbe O(1)+O(n) = O(n)
è semplicemente così o dimentico qualcosa?

---------------------------------------

int fun(int a[], int n) {
int i,j,k,tot;
if(n<3) return 0;
for(i=0;i<2;i++) {
a[i]++;
for(j=0;j<n;j++)
a[j] += a[i];
for(k=1;k<n-1;j++)
a[i] += a[k];
}
return fun(a,2*n/3) + 2 * fun(a+n/3,2*n/3);
}

fun(a+n/3,2*n/3) significa la funzione sun applicata all’array a a partire dall’elemento n/3 e con
secondo parametro 2*n/3

O(1)+O(2)+O(n)+O(n-2)=O(n^2)
però non ne sono sicuro,mi date conferme?

Colgo l' occasione per fare gli Auguri di Buone Feste a tutte le persone del Forum

Grazie in anticipo

[Alex'87]

Se indentassi il codice si capirebbe qualcosa...

[gabama]

chiedo scusa,spero vada meglio adesso

int fun(int a[], int n) {
 int i;
 if(n<2) return a[0];
     for(i=1;i<n;i++)
     a[i] = a[i]-a[i-1];
 return fun(a,1) + fun(a,n-1);
}

-----------------------------------------

int fun(int a[], int n) {
 int i,j,k,tot;
 if(n<3) return 0;
     for(i=0;i<2;i++) {
     a[i]++;
          for(j=0;j<n;j++)
          a[j] += a[i];
                  for(k=1;k<n-1;j++)
                  a[i] += a[k];
}
 return fun(a,2*n/3) + 2 * fun(a+n/3,2*n/3);
}

[gabama]

nessuno?

[Alex'87]

Originariamente inviato da gabama
sarebbe O(1)+O(n) = O(n)
è semplicemente così o dimentico qualcosa?

:master:
Più di tanto non me ne intendo ma... non dovresti considerare anche la chiamata ricorsiva?

[xnavigator]

algoritmi e basi dati è una brutta bestia lo so

[ZannaZ]

Originariamente inviato da gabama
Buonasera,mi sono trovato a ragionare su questi 2 algoritmi e vorrei delle conferme,se possibile,sulla complessità

int fun(int a[], int n) {
  int i;
  if(n<2) return a[0];
  for(i=1;i<n;i++)
    a[i] = a[i]-a[i-1];
  return fun(a,1) + fun(a,n-1);
}

sarebbe O(1)+O(n) = O(n)
è semplicemente così o dimentico qualcosa?

Dimentichi sì qualcosa: tu esegui la chiamata ricorsiva di questa funzione ~n volte su un input ogni volta più piccolo di una unità (per ognuna di queste chiamate in realtà esegui anche un'altra chiamata fun(a,1), ma la possiamo trascurare perché il suo tempo di calcolo è costante e quindi essendo ripetuta n volte ha complessità O(n) che è asintoticamente trascurabile nel nostro caso).
Di conseguenza abbiamo una sommatoria per i da 1 a n di {O(i) (=fun(a,n-1)) + O(1) (=fun(a,1)) }
Quindi T(n) = O(n^2) + O(n) = O(n^2)
Tutto questo l'ho fatto al volo e spero di non aver detto ca**ate, quindi prendetelo con il beneficio del dubbio.

EDIT: in teoria si dovrebbe risolvere una semplice equazione di ricorrenza per calcolare T(n) ma ho evitato perché trovo che così spiegato sia più intuitivo.

[xnavigator]

concordo anche perchè di solito quando ci sono 2 chiamate ricorsive la complessità difficilimente sarà solo lineare

[ZannaZ]

Originariamente inviato da xnavigator
concordo anche perchè di solito quando ci sono 2 chiamate ricorsive la complessità difficilimente sarà solo lineare

mmm.. non è detto: se eliminassimo il ciclo for per es. avremmo una complessità lineare se non sbaglio.
Cmq sì è difficile, più che altro perché solitamente quando ci sono due chiamate ricorsive normalmente nessuna di queste viene eseguita in un tempo costante, invece nel nostro fun(a,1) "matcha" proprio la condizione di uscita.

[gabama]

grazie davvero ragazzi,e il secondo?Come mi comporto per l' ultima chiamata?