Complessità temporale di un algoritmo ricorsivo

Question

Come posso calcolare la complessità temporale di un algoritmo ricorsivo?

int pow1(int x,int n) { 
    if(n==0){ 
     return 1; 
    } 
    else{ 
     return x * pow1(x, n-1); 
    } 
} 

int pow2(int x,int n) { 
    if(n==0){ 
     return 1; 
    } 
    else if(n&1){ 
     int p = pow2(x, (n-1)/2) 
     return x * p * p; 
    } 
    else { 
     int p = pow2(x, n/2) 
     return p * p; 
    } 
} 

Answer 1

Analizzando funzioni ricorsive (o anche la loro valutazione) è un compito non banale. a (a mio parere) buona introduzione può essere trovato in Don Knuths Concrete Mathematics.

Tuttavia, analizziamo questi esempi ora:

Definiamo una funzione che ci dà il tempo necessario a una funzione. Diciamo che t(n) indica il tempo necessario da pow(x,n), ad esempio una funzione di n.

Quindi possiamo concludere che t(0)=c, perché se chiamiamo pow(x,0), dobbiamo verificare se (n==0), e poi tornare 1, che può essere fatto in tempo costante (da qui la costante c).

Ora consideriamo l'altro caso: n>0. Qui otteniamo t(n) = d + t(n-1). Questo perché dobbiamo nuovamente controllare n==1, calcolare , quindi (t(n-1)) e moltiplicare il risultato per x.Il controllo e la moltiplicazione possono essere eseguiti in tempo costante (costante d), il calcolo ricorsivo di pow ha bisogno di t(n-1).

Ora possiamo "espandere" il termine t(n):

t(n) = 
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) = 
... = 
d + d + d + ... + t(1) = 
d + d + d + ... + c 

Così, quanto tempo ci vuole fino a raggiungere t(1)? Poiché iniziamo allo t(n) e sottraiamo 1 in ogni passaggio, sono necessari i passi n-1 per raggiungere t(n-(n-1)) = t(1). Ciò significa che otteniamo n-1 volte la costante d e t(1) è valutata a c.

Così otteniamo:

t(n) = 
... 
d + d + d + ... + c = 
(n-1) * d + c 

Così otteniamo che t(n)=(n-1) * d + c che è elemento di O (n).

pow2 può essere utilizzato utilizzando Masters theorem. Dal momento che possiamo assumere che le funzioni temporali per gli algoritmi stiano aumentando monotonicamente. Così ora abbiamo il tempo t(n) necessario per il calcolo di pow2(x,n):

t(0) = c (since constant time needed for computation of pow(x,0)) 

per n>0 otteniamo

 /t((n-1)/2) + d if n is odd (d is constant cost) 
t(n) = < 
     \ t(n/2) + d  if n is even (d is constant cost) 

È possibile che questo può essere "semplificato" a:

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing) 

Così abbiamo ottenere t(n) <= t(n/2) + d, che può essere risolto utilizzando il teorema dei master su t(n) = O(log n) (vedere la sezione Applicazione a Popul ar Algoritmi nel collegamento wikipedia, ad esempio "Ricerca binaria").

Answer 2

Può essere un po 'complessa, ma penso che il modo usuale è quello di utilizzare Master's theorem.

Answer 3

complessità di entrambe le funzioni ignorando ricorsione è O (1)

Per la prima pow1 algoritmo (x, n) la complessità è O (n) per la profondità di ricorsione correla con n linearmente.

Per la seconda complessità è O (log n). Qui riceviamo circa log2 (n) volte. Buttando fuori 2 otteniamo il registro n.

Answer 4

Quindi immagino che stai aumentando x alla potenza n. pow1 richiede O (n).

Non si modifica mai il valore di x ma si prende 1 da n ogni volta finché non arriva a 1 (e si ritorna quindi) Ciò significa che si effettuerà una chiamata ricorsiva n volte.

Answer 5

Iniziamo con pow1, perché è il più semplice.

Si dispone di una funzione in cui viene eseguita una singola corsa in O (1). (Il controllo delle condizioni, il ritorno e la moltiplicazione sono costanti.)

Quello che ti rimane è la tua ricorsione. Quello che devi fare è analizzare quanto spesso la funzione finirà per chiamarsi. In pow1, succederà N volte. N * O (1) = O (N).

Per pow2, è lo stesso principio: una singola esecuzione della funzione viene eseguita in O (1). Tuttavia, questa volta stai dimezzando N ogni volta. Ciò significa che verrà eseguito log2 (N) volte - efficacemente una volta per bit. log2 (N) * O (1) = O (log (N)).

Qualcosa che potrebbe aiutare voi è quello di sfruttare il fatto che la ricorsione può sempre essere espressa come iterazione (non sempre in modo molto semplice, ma è possibile. Possiamo esprimere pow1 come

result = 1; 
while(n != 0) 
{ 
    result = result*n; 
    n = n - 1; 
} 

Ora avete un algoritmo iterativo invece, e si potrebbe trovare più facile da analizzare in questo modo.

Answer 6

Questo collegamento fornisce la risposta esatta al problema. Ecco la fonte (http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf)