Il tuo codice ricorsivo corrente è leggermente errato, perché il tipo di mid è int e non float . Una volta corretto, una versione ricorsiva dell'algoritmo iterativo è:
final static float EPSILON = 0.00001;
static float sqrt(float n) {
// Here, I use high = n for simplicity's sake.
// In a real application, I'd special-case n = 0, …, 4
// and start with high = n/2
return recursiveSqrt(n, 0, n);
}
static float recursiveSqrt(float n, float low, float high) {
float mid = (low + high) / 2;
float midSquare = mid * mid;
// This is the base case of the recursion
// which corresponds to a loop condition.
if (math.abs(midSquare - n) < EPSILON) return mid;
// Anything that's not the base case recurses.
// Here, we recurse either into the left or right half
// of the currently processed interval
if (midSquare > n) return recursiveSqrt(n, low, mid);
else return recursiveSqrt(n, mid, high);
}
Ora, il Teorema principale non è interessato all'implementazione specifica della funzione ricorsiva, ma in tre proprietà:
- Qual è il tempo di esecuzione in ogni fase, esclusa la ricorsione?
- Quanto spesso ricicliamo per invocazione?
- In che modo le dimensioni del problema si riducono a ogni invocazione?
Insieme, definiscono i parametri f (n) , a e b nell'equazione del teorema principale
T(n) = a · T(n/b) + f(n)
che descrive la complessità di alcune funzioni ricorsive. Si noti che la funzione f(n) è anche un'espressione di complessità. Descrive l'overhead di iterazione, che può dipendere dalla dimensione del problema in ogni iterazione.
La risposta alla prima domanda è che ogni invocazione ha un tempo di esecuzione costante (esclusa la ricorsione), poiché gli operatori aritmetici, gli operatori di confronto e Math.abs() richiedono tempo costante. L'unico modo per avere un tempo non costante è usare i loop o invocare una funzione o un metodo che ha un tempo non costante - e non facciamo nulla di tutto ciò. Pertanto, f(n) = O(1) .
Successivamente, dobbiamo determinare la frequenza con cui ci rechiamo. Mentre il codice contiene due invocazioni della funzione ricorsiva, solo una di esse verrà eseguita in qualsiasi iterazione. Quindi a = 1 .
Infine, dobbiamo considerare la dimensione del problema. La dimensione del problema di ogni iterazione è non il nostro parametro n . Invece, è l'intervallo high - low . Ad ogni iterazione, dimezza questo intervallo calcolando il punto medio. Pertanto, b = 2 . Non importa dove sia questo intervallo e se un'iterazione preleva la metà inferiore o superiore. Conta solo la dimensione della gamma. La dimensione iniziale dell'intervallo è n .
Ora abbiamo determinato tutti i parametri necessari per applicare il Teorema Master.
I nostri parametri non corrispondono al primo caso in cui f(n) = O(nc) per alcuni parametri c con c < logb(a) : qui abbiamo c = logb(a) = 0 .
Tuttavia, corrisponde immediatamente al secondo caso in cui f(n) = Θ(nc · logk(a)) con k ≥ 0 e c = logb(a) (Il carattere Θ che assomiglia a uno zero è in realtà la lettera greca maiuscola Theta). Qui, c = k = 0 .
Quindi, la complessità totale è T(n) = Θ(nc · logk + 1(n)) = Θ(log n) .
Interpretazione: questo metodo per approssimare una radice quadrata è essenzialmente una ricerca binaria sulla sequenza ordinata di tutti i numeri tra zero e n . Questa sequenza è discreta e tutti i numeri nella sequenza sono 2·epsilon a parte. Ad ogni iterazione, abbiamo limiti inferiori e superiori che delimitano una sottolista che deve contenere l'elemento della lista ricercata. Poiché la sequenza è ordinata, guardiamo l'elemento nel mezzo della sottodirectory e quindi continuiamo a cercare nella sottolista sinistra o destra, a seconda che l'elemento centrale sia più grande o più piccolo dell'elemento desiderato. Di conseguenza, questo algoritmo deve avere le stesse caratteristiche di complessità temporale di una ricerca binaria.