Ciao a tutti ragazzi! Avrei bisogno di aiuto con il calcolo del costo asintotico dell’algoritmo ternsearch(int a[], int v). è una variazione di un’ordinaria ricerca binaria ma divide l’array in input in 3 parti.
Sapreste aiutarmi?
Grazie a tutti!
static int ternsearch(int a[], int v, int start, int end) { // array a ordinato in senso non decrescente
if (end - start < 2) return base(a, v, start, end);
int onethird = (end - start)/3;
int i = start + onethird;
if(a[i] > v) return ternsearch(a, v, start, i-1);
else if (a[i] == v) return i;
else {
int j = i + onethird;
if(a[j] > v) return ternsearch(a, v, i+1, j-1);
else if (a[j] == v) return j;
else return ternsearch(a, v, j+1, end);
}
}
static int base(int a[], int v, int start, int end) { // array a ordinato in senso non decrescente
while(start <= end) {
if(a[start] == v) return start;
start++;
}
return -1;
}
static int ternsearch(int a[], int v) { // array a ordinato in senso non decrescente
return ternsearch(a, v, 0, a.length-1);
}
Ad ogni richiamo scomponi l’intervallo grande N in uno grande N/3, sono necessari quindi log₃N passaggi, ognuno dei quali utilizza un tempo asintoticamente costante, la complessità è quindi O(log₃N)
Per completezza: la complessità computazionale è teoricamente inferiore alla complessità della ricerca binaria ma nella pratica le prestazioni non mostrano differenze rilevanti su input di grandezze ragionevoli.
Tecnicamente la complessità è la stessa perché il logaritmo in base 3 differisce da quello in base 2 per una costante c, per l’esattezza c = \frac1{\log_2 3} \approx 0.63093
Quindi è corretto anche dire che O(\log_3 n) = O(\log_2 n) = O(\log n).