Complessità Ricorsiva

[alexover]

Salve a tutti, oggi mi sono imbattuto in un calcolo del tempo di esecuzione nel caso peggiore di questo codice:

public static boolean ElementInComune(int a[],int n,int b[],int i,int j){
	if (i==j) {
	for (int k=0; k<n; k++){
		if (a[k]==b[i]){
			return true;
		}
	}
	return false;
	} else {
		int m=(i+j)/2;
		if (ElementInComune(a,n,b,i,m)) return true;
		else return ElementInComune(a,n,b,m+1,j);
	}
	
}

Il caso peggiore dovrebbe essere quando i due array, entrambi di lunghezza n hanno elementi tutti differenti.
La parte dell'else sembra venga eseguita prima n/2 volte, poi n/2 - 1 volte, eseguendo il codice si nota anche che il for (int k ecc...) viene eseguito n/2 volte sia per n/2 sia per n/2-1... qualcosa come n/2*(n/2)+n/2*(n/2)-1...
Ok basta supposizioni sennò dico altre fesserie

[vict85]

Il codice non è ben indentato, ho dovuto controllare tutte le graffe per capirlo...

In ogni caso il caso peggiore è quando non ci sono elementi in comune, in quel caso la complessità è \(O(ns\), con s = \(j-i\) perché deve farli tutti. Il codice comunque fa pena perché, di fatto, controlla tutti gli elementi in ordine anche se fa credere che cerchi l'elemento con un binary search. In realtà però continua a ridurre la dimensione dell'intervallo fino a che diventa di un elemento, poi sale l'albero e controlla l'elemento successivo, poi sale nuovamente e scende fino a prendere in terzo e così via.

Questo codice:

for(int k = i; k<=j; k++)
{
  for(int s= 0; s<n; s++)
  {
    if(a[s] == a[k]) return true;
  }
}
return false;

è equivalente al tuo e fa meno chiamate a funzione.

[vict85]

Comunque se vuoi il numero esatto di operazioni sarebbe:

\(m\) confronti ogni elemento di \(j-i\) e, supponendo che \(j-i = 2^s\) si hanno \(1 + 2 + 4 + \dots + 2^{s}\) chiamate a funzione, cioè \(\displaystyle \frac{2^{s+1}-1}{2-1} = 2(j-i) - 1\). Il calcolo si può fare anche nel caso generico.