Big O per la funzione di ricorsione

Question

So che quando si divide la dimensione del problema impostato in una frazione specificata si ha a che fare con O (log (n)). Tuttavia sono confuso quando sono più di 1 chiamate ricorsive che fanno questo. Ad esempio in questa funzione qui andremo a calcolare il valore di un esponente.

public static long pow(long x, int n) 
    { 
     if(n==1) 
     return x; 
     if(isEven(n)) 
     return pow(x,n/2) * pow(x,n/2); 
     else 
     return pow(x*x, n/2) * x 
     } 

Dopo aver eseguito l'analisi, ho ottenuto il tempo di esecuzione uguale a O (N). Ho ragione? Grazie per il tuo tempo

Answer 1

Sì, sei corretto, almeno sotto analisi del caso peggiore.

Si noti che per n = 2^k, per alcuni naturali k, si ottiene che, ad eccezione quando si raggiunge la clausola di stop, la condizione è sempre vero, e la funzione ricorsiva sarà corse due volte.

Quando ciò è stabilito, è sufficiente analizzare:

T(n) = T(n/2) + T(n/2) + X 

Dove X è una costante, (ogni chiamata ricorsiva prende costante quantità di lavoro, se ignorando le altre chiamate ricorsive).

Da master theorem case 1, con:

f(n) = X 
a = 2, b = 2, c = 0 (since X is in O(n^0)=O(1)) 

E poiché c=0 < 1 = log_2(2), condizioni per caso 1 si applicano, e possiamo concludere la funzione T(n) è in Theta(n^log_2(2)) = Theta(n)

analisi media caso:

Nel caso medio, con il numero uniformemente distribuito n, la metà dei bit nel binario rappresenta questo numero sarà attivo (1) e metà sarà "in basso" (0).

Dal dividendo per 2 è sostanzialmente aritmetica spostamento a destra, e la condizione isEven(n) vale se e solo se il bit meno significativo è 0, ciò significa che la funzione media complessità è:

T(n) = 0.5 T(n/2) + 0.5 * 2 T(n/2) + X = 0.5 * 3 * T(n/2) + X 
    = 1.5 * T(n/2) + X 

Così

T(n) = 3/2 T(n/2) + X 

Caso 1 si applica ancora (supponendo costante X):

a = 3/2, b = 2, c = 0

e si ottiene caso la complessità media di Theta(n^log_1.5(2))~=Theta(n^0.58)

rapida Nota:

Questo presuppone in effetti tutti i aritmetica sono O(1). Se questo non è il caso (numeri molto grandi), dovresti inserire la loro complessità invece della costante nella definizione di T(n) e rianalizzare. Supponendo che ciascuna di queste operazioni sia sub-lineare (nel numero, non nei bit che la rappresentano), il risultato rimane Theta(n), poiché si applica ancora il caso 1 del teorema master. (Nel caso medio, per qualsiasi funzione "migliore" di non cambierà il risultato mostrato

Answer 2

Varun, si è parzialmente corretti.Vediamo i due casi:

1. se n è pari, allora siete proprio dividendo il compito in due metà, senza ottimizzare in modo significativo, dal momento che pow(x, n/2) è calcolato due volte.

2. Se n è dispari, si ha un caso speciale di scomposizione. x sarà sostituito da x x, che rende x x la nuova base, che ti evita di ricalcolare x * x.

Nel primo caso abbiamo una leggera ottimizzazione, poiché è più facile ripetere le produzioni più piccoli di fare il tutto, come:

(3 * 3 * 3 * 3) * (3 * 3 * 3 * 3) è più facile da calcolare rispetto a (3 * 3 * 3 * 3 * 3 * 3 * 3 * 3), quindi il primo caso migliora leggermente il calcolo utilizzando il fatto che la produzione è un'operazione associativa. Il numero di produzione eseguita nel primo caso non è ridotto, ma il modo in cui viene eseguito il calcolo è migliore.

Nel secondo caso, tuttavia, si dispone di significative ottimizzazioni. Supponiamo che sia n = (2^p) - 1. In tal caso, riduciamo il problema a un problema, dove n = ((2^p - 1) - 1)/2 = ((2^p) - 2)/2 = (2^(p-1)) - 1. Quindi, se p è un numero naturale e n = (2^p) - 1, lo stai riducendo a metà. Quindi, l'algoritmo è logaritmico nel migliore dei casi n = (2^p) - 1 ed è lineare nello scenario peggiore n = 2^p.

Answer 3

Di solito analizziamo la complessità del caso peggiore, che si verifica quando isEven (n) è true. In tal caso, abbiamo

T(n) = 2T(n/2) + O(1) 

dove T (n) indica la complessità temporale di pow (x, n).

Applicare Master theorem, Case 1 per ottenere la forma di notazione Big-O di T (n). Cioè:

T(n) = O(n)