Complessità temporale di un algoritmo ricorsivo

Analizzare le funzioni ricorsive (o anche valutarle) è un compito non banale. A (secondo me) una buona introduzione può essere trovata in Don Knuths Concrete Mathematics .

Tuttavia, analizziamo questi esempi ora:

Definiamo una funzione che ci dà il tempo necessario per una funzione. Diciamo che t(n) denota il tempo richiesto da pow(x,n) , cioè una funzione di n .

Quindi possiamo concludere, che t(0)=c , perché se chiamiamo pow(x,0) , dobbiamo controllare se ( n==0 ), e quindi restituire 1, che può essere fatto in tempo costante (quindi la costante c ).

Ora consideriamo l’altro caso: n>0 . Qui otteniamo t(n) = d + t(n-1) . Questo perché dobbiamo ancora controllare n==1 , calcolare pow(x, n-1 , 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 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 

Quindi, quanto ci vuole prima che raggiungiamo t(1) ? Dato che iniziamo con t(n) e sottraiamo 1 in ogni passo, ci vogliono n-1 passi per raggiungere t(n-(n-1)) = t(1) . Questo, d’altra parte, significa che otteniamo n-1 volte la costante d , e t(1) è valutata a c .

Quindi otteniamo:

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

Quindi otteniamo che t(n)=(n-1) * d + c che è l’elemento di O (n).

pow2 può essere fatto usando il teorema di Masters . Dal momento che possiamo assumere che le funzioni temporali per gli algoritmi stiano aumentando monotonicamente. Quindi 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) 

Quanto sopra può essere "semplificato" per:

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

Quindi otteniamo t(n) <= t(n/2) + d , che può essere risolto usando il teorema dei maestri a t(n) = O(log n) (vedere la sezione Applicazione agli algoritmi più popolari nel collegamento wikipedia, esempio "Ricerca binaria").

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

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

Ciò che ti rimane è quindi 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 aiutarti è sfruttare il fatto che la ricorsione può sempre essere espressa come iterazione (non sempre molto semplicemente, ma è ansible. Possiamo esprimere pow1 come

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

Ora hai invece un algoritmo iterativo e potresti trovare più facile analizzarlo in questo modo.

Può essere un po ‘complesso, ma penso che il modo usuale sia usare il teorema del Maestro .

La complessità di entrambe le funzioni che ignorano la ricorsione è O (1)

Per il primo algoritmo pow1 (x, n) la complessità è O (n) perché la profondità della ricorsione è correlata con n in modo lineare.

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

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

Non cambi mai il valore di x ma prendi 1 da n ogni volta fino a che non arriva a 1 (e poi torni indietro) Ciò significa che effettuerai una chiamata ricorsiva n volte.